COMMENT ⊗   VALID 00019 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	%folio 763 galley 1 (C) Addison-Wesley 1978 	-
C00013 00003	%folio 763a galley 2 NOTE: much tape unreadable (C) Addison-Wesley 1978 	-
C00018 00004	%folio 768 galley 3a (C) Addison-Wesley 1978	-
C00025 00005	%folio 769 galley 3b (C) Addison-Wesley 1978	-
C00032 00006	%folio 770 galley 4 (C) Addison-Wesley 1978	-
C00043 00007	%folio 771 galley 5 (C) Addison-Wesley 1978	-
C00056 00008	%folio 776 galley 6a (C) Addison-Wesley 1978	-
C00063 00009	%folio 777 galley 6b (C) Addison-Wesley 1978	-
C00068 00010	%folio 777 galley 7 Bad beginning. (C) Addison-Wesley 1978	-
C00077 00011	%folio 781 galley 8 (C) Addison-Wesley 1978	-
C00088 00012	%folio 784 galley 9 (C) Addison-Wesley 1978	-
C00103 00013	%folio 790 galley 10 (C) Addison-Wesley 1978	-
C00115 00014	%folio 794 galley 11a (C) Addison-Wesley 1978	-
C00123 00015	%folio 795 galley 11b (C) Addison-Wesley 1978	-
C00127 00016	%folio 796 galley 11c (C) Addison-Wesley 1978	-
C00134 00017	%folio 797 galley 12 (C) Addison-Wesley 1978	-
C00148 00018	%folio 800 galley 13 (C) Addison-Wesley 1978	-
C00156 00019	
C00157 ENDMK
C⊗;
%folio 763 galley 1 (C) Addison-Wesley 1978 	-
|newtype 58320---Computer Programming\quad (Knuth/A.-W.)\quad
ch. 4\quad f. 763\quad g. 1c
$$|newtype {\:r SECTION 4.3.3

|qleft }\12skip |newtype ??M21}|tab \qquad \qquad \qquad \quad
|tab \qquad \qquad \qquad \quad |tab \qquad \qquad \qquad \quad
\ansno 1. 27 \times
47:⊗18 \times 42:⊗09 \times 05:⊗2718 \times 4742:\cr
\qquad 08 ⊗04 ⊗00 ⊗1269\qquad \cr
\qquad 08 ⊗04⊗00⊗\quad 1269 \cr
\qquad 15⊗14⊗45⊗ -0045 \cr
\qquad 49⊗16⊗45⊗0756\cr
\qquad 49⊗ 16⊗ 45⊗\qquad 0756\cr
\4skip \qquad 1269⊗0756⊗0045⊗12888756\cr

\ansno 2. K|newtype \sqrt{$Q + \lfloor \sum Q\rfloor
} ≤ |newtype \sum |newtype \sqrt{Q + \sum Q} < |newtype \sum
|newtype \sqrt{Q + 2\sum Q + 1} = \sum \sqrt{Q} + 1$, so $\lfloor
\sum \sqrt{Q + R}\rfloor ≤ \lfloor \sum \sqrt{Q}\rfloor + 1$.

\ansno 3. When $k ≤ 2$, the result is
true, so assume that $k > 2$. Let $q↓k = 2↑Q|infsup k, r↓k =
2↑R|infsup k$, so that $R↓k = \lfloor \sum \sqrt{Q↓k}\rfloor$
and $Q↓k = Q↓{k-1} + R↓{k-1}$. We must show that $1 + (R↓k +
1)2↑R|infsup k ≤ 2↑Q|infsup k|infsup -|infsup 1$; this inequality
isn't close at all, one way is to observe that $1 + (R↓k + 1)2↑R|infsup
k ≤ 1 + 2↑{2R}|infsup k$ and $2R↓k < Q↓{k-1}$ when $k > 2$.
(The fact that $2R↓k < Q↓{k-1}$ is readily proved by induction
since $R↓{k+1} - R↓k ≤ 1$ and $Q↓k - Q↓{k-1} ≥ 2.)$

\ansno 4. For $j = 1$, $\ldotss$, $r$, calculate $U↓e(j↑2),
jU↓o(j↑2), V↓e(j↑2), jV↓o(j↑2)$; and by recursively calling
the multiplication algorithm, calculate
$$
|qctr \hfill W(j) ⊗= \biglp U$↓e(j↑2) + jU↓o(j↑2)|newtype )(|newtype
V↓e(j↑2) + jV↓o(j↑2)\bigrp ,\cr
\4skip \hfill W(-j) ⊗= \biglp U↓e(j↑2) - jU↓o(j↑2)|newtype )(|newtype
V↓e(j↑2) - jV↓o(j↑2)\bigrp ;\cr
\9skip$ and then we have $W↓e(j↑2) = {1\over 2}\biglp W(j) +
W(-j)\bigrp , W↓o(j↑2) = {1\over 2}\biglp W(j) - W(-j)\bigrp
$. Also calculate $W↓e(0) = U(0)V(0)$. Now construct difference
tables for $W↓e$ and $W↓o$, which are polynomials whose respective
degrees are $r$ and $r - 1$.

This method reduces the size of the numbers being
handled, and reduces the number of additions and multiplications.
Its only disadvantage is a longer program (since the control
is somewhat more complex, and some of the calculations must
be done with signed numbers).
|qleft |newtype \qquad Another possibility would perhaps be
to evaluate $W↓e$ and $W↓o$ at 1$↑2, 2↑2, 4↑2, \ldotss , (2↑r)↑2$;
although the numbers involved are larger, the calculations are
faster, since all multiplications are replaced by shifting and
all divisions are by binary numbers of the form $2↑j(2↑k - 1).
($Simple procedures are available for dividing by such numbers.)

\ansno 5. Start the $q, r$ sequences out with $q↓0,
q↓1$ large enough so that the inequality in exercise 3 is valid.
Then we will find in the formulas analogous to those preceding
Theorem C that $\eta ↓1 → 0$ and $\eta ↓2 = (1 + 1/2r↓k)2↑{1
+ 2Q↓k-2Q↓{k+1}}(Q↓k/Q↓{k+1})$. The factor $Q↓k/Q↓{k+1} → 1$
as $k → ∞$, so we can ignore it if we want to show $\eta ↓2
< 1 - ε$ for all large $k$. Now $\sqrt{2Q↓{k+1}} = |newtype
|newtype \sqrt{2Q↓k + 2\lceil 2Q↓k\rceil + 2} ≥ |newtype |newtype
\sqrt{(2Q↓k + 22Q↓k + 1) + 1 ≥ 2Q↓k + 1 + 1/3R↓k$. Hence $\eta
↓2 ≤ (1 + 1/2r↓k)2↑{-1/3R}|infsup k$, and lg $\eta ↓2 < 0$ for
large enough $k$.

Note{\sl : }Algorithm C can also be modified to
define a sequence $q↓0, q↓1, . . $. of a similar type that
is based on $n$, so that $n \approx q↓k + q↓{k+1}$ after step
C1. (Algorithm S essentially does this.) This would establish
(19).

\ansno 6. Any common divisor of
$6q + d↓1$ and $6q + d↓2$ must also divide their difference
$d↓2 - d↓1$. The $6\choose2$ differences are 2, 3, 4, 6,
8, 1, 2, 4, 6, 1, 3, 5, 2, 4, 2, so we must only show that at
most one of the given numbers is divisible by each of the primes
2, 3, 5. Clearly only $6q + 2$ is even, and only $6q + 3$ is
a multiple of 3; and there is at most one multiple of 5, since
$q↓k |spose ??≡ 3\modulo 5$.

\ansno 7. $t↓k ≤ 6t↓{k-1} + ck3↑k$ for some constant $c$; so
$t↓k/6↑k ≤ t↓{k-1}/6↑{k-1} + ck/2↑k ≤ t↓0 + c \sum ↓{j≥1 (j/2↑j)
= M$. Thus $t↓k ≤ M \cdot 6↑k$.

\ansno 8. The analog of Eq.\ (39) would break down.
In fact it is impossible to ``untransform'' the finite Fourier
transform of $(a↓0, a↓1, a↓2, a↓3)$ mod 15 when $\omega = 2$,
since information is lost during the transformation process.

\ansno 9. $Ku↓{(-r)$ mod $K}$.

\ansno 10. The lower bound ensures that $??3 + 2 < n$, so the
products $|spose ---U↓t|spose ---V↓t$ have fewer bits than the
product {\sl uv.} The upper bound comes from the definition
of $\omega $. [Sch|spose 4onhage observes that we could actually
allow $k = ??3 + 4$, since $(2↑{3\2}|supsup n|supsup -|supsup
2 - 2↑2|supsup n|supsup -|supsup 2)↑2 ≡ 2\modulo{2$↑2|supsup
n + 1).]$

\ansno 11. An automaton cannot have $z↓2 = 1$ until it has $c
≥ 2$, and this occurs first for $M↓j$ at time $3j - 1$. It follows
that $M↓j$ cannot have $z↓2z↓1z↓0 ≠ 000$ until time $3(j - 1)$.
Furthermore, if $M↓j$ has $z↓0 ≠ 0$ at time $t$, we cannot change
this to $z↓0 = 0$ without affecting the output; but the output
cannot be affected by this value of $z↓0$ until at least time
$t + j - 1$, so we must have $t + j - 1 ≤ 2n$. Since the first
argument we gave proves that $3(j - 1) ≤ t$, we must have $4(j
- 1) ≤ 2n$, that is, $j - 1 ≤ n/2$, i.e., $j ≤ \lfloor n/2\rfloor
+ 1$.

Furthermore, this is the best possible bound,
since the inputs $u = v = 2↑n - 1$ require the use of $M↓j$
for all $j ≤ \lfloor n/2\rfloor + 1$. (For example, note from
Table 1 that $M↓2$ is needed to multiply two-bit numbers, at
time 3.)

\ansno 13. If it takes $T(n)$ cycles to multiply
$n$-bit numbers, we can accomplish the multiplication of $m$-bit
by $n$-bit by breaking the $n$-bit number into \lceil $n/m\rceil
m$-bit groups, using $\lceil n/m\rceil T(m) + O(n + m)$ operations.
The results of this section therefore give an estimated running
time of $O(n$ log $m$ log log $m)$.
%folio 763a galley 2 NOTE: much tape unreadable (C) Addison-Wesley 1978 	-

|qleft \24skip |newtype {\:r SECTION 4.4

\ansno 1. We compute $\biglp \ldotsm (a↓mb↓{m-1}
+ a↓{m-2})b↓{m-2} +\cdots + a↓1\bigrp b↓1 + a↓0$
by adding and multiplying in the $B↓j$ system.

|qleft \9skip ??M25.6}|tab \qquad \qquad \qquad \qquad \quad
|tab \qquad |tab \qquad \qquad \qquad |tab \qquad \qquad \quad
|tab \qquad \qquad \quad |tab \qquad \qquad \qquad \quad |tab
|zfa ⊗⊗T.⊗= 20(cwt.⊗= 8(st.⊗= 14(lb.⊗= 16 oz.)))\cr
\2skip Start with zerDivide by ∞⊗0⊗0⊗ 0⊗ 0⊗Remainder = 8\cr
\12skip {\sl Answer{\sl : }}8 T. 3 cwt. 1 st. 2 lb. 5 oz.

\ansno 3. [{\sl CACM \bf 2}, 7 (July 1959), 27.]
|qleft |indent |newtype \qquad (Note{\sl :} It is possible for
this algorithm to yield $U = 1$; if this is undesirable, we
could modify the algorithm as follows: In step A1, set a new
variable $t ← 1$. In step A2, do not go to A4 if $t = 1$. In
step A3, set $t ← 0$ if $U↓{-k} ≠ B - 1$. The re\9skip $1/10
- 2↑{-35} < α = (.000110011001100110011001100110011)↓2 < 1/10$,
|qctr \9skip we find that $αu - ε ≤ v ?? αu$ at the end of the
computation, where
$$$ε = {7\over 8} + (.100010001010100011001000101010001)↓2 <
{3\over 2}$.
|qctr \9skip Hence $u/10 - 2 < u/10 - \biglp ε + (1/10 - α)u\bigrp
≤ v ≤ αu < u/10$. Since $v$ is an integer, the proof is complete.

\ansno 10. (a) Shift right one;\xskip (b) Extract left bit of each
group;\xskip (c) Shift result of (b) right two;\xskip (d) Shift result of
(c) right one, and add to result of (c);\xskip (e) Subtract result
of (d) from result of (a).

\ansno 11.
⊗⊗5.7 7 2 1\cr
⊗- 1 0\cr
\4skip ⊗⊗4 7.7 2 1\cr
⊗- 9 4\cr
\4skip ⊗⊗3 8 3.2 1\cr
⊗- 7 6 6\cr
\4skip ⊗⊗3 0 6 6.1\cr
⊗- 6 1 3 2\cr
\4skip ⊗⊗2 4 5 2 9\qquad {\sl Answer{\sl : }}(24529)$↓{10}$.

\ansno 12. First convert the ternary number
to nonary (radix 9) notation, then proceed as in octal-to-decimal
conversion but without doubling. Decimal to nonary is similar.
In the given example, we have
$$
|qleft ⊗1.7 6 4 7 2 3\cr
- 1\cr
\4skip ⊗1 6.6 4 7 2 3\cr
- 1 6\cr
\4skip ⊗1 5 0.4 7 2 3\cr
- 1 5 0\cr
\4skip ⊗1 3 5 4.7 2 3\cr
- 1 3 5 4\cr
\4skip ⊗1 2 1 9 3.2 3\cr
- 1 2 1 9 3\cr
\4skip ⊗1 0 9 7 3 9.3\cr
- 1 0 9 7 3 9\cr
\4skip ⊗ 9 8 7 6 5 4\qquad {\sl Answer{\sl : }}(987654)$↓{10}$.

|qleft \12skip ⊗ 9.8 7 6 5 4\cr
+ 9

|qleft \4skip ⊗1 1 8.7 6 5 4\cr
+ 1 1 8

|qleft \4skip ⊗1 3 1 6.6 5 4\cr
+ 1 3 1 6

|qleft \4skip ⊗1 4 4 8 3.5 4\cr
+ 1 4 4 8 3

|qleft \4skip ⊗1 6 0 4 2 8.4\cr
+ 1 6 0 4 2 8

|qleft \4skip ⊗1 7 6 4 7 2 3\qquad {\sl Answer{\sl : }}(1764723)$↓9$.

|qleft \12skip |newtype ???|newtype 58320---Computer Programming\quad
%folio 768 galley 3a (C) Addison-Wesley 1978	-
(Knuth/A.-W.)\quad f. 768\quad ch. 4\quad g. 3c
$$|newtype |tab \qquad |tab \qquad \qquad |tab \qquad \qquad
|tab \qquad \qquad \qquad \qquad \qquad \qquad \quad |tab \qquad
\ansno 13. ⊗BUF1⊗ALF⊗.⊗(Radix
point on first line)\cr
⊗⊗ORIG⊗ +23⊗\cr
⊗BF2⊗ORIG⊗ +24\cr
⊗START⊗JOV⊗OFLO⊗Ensure overflow is off.\cr
⊗⊗ENT2⊗BUF1??BUF2⊗Set buffer pointer.\cr
⊗8H⊗ENT3⊗10⊗Set loop counter.\cr
⊗1H⊗ENT1⊗$m⊗$Begin multiplication routine.\cr
⊗⊗ENTX⊗0\cr
⊗2H⊗STX⊗CARRY\cr
⊗⊗. . .⊗⊗(See exercise 4.3.1--13, with\cr
⊗⊗JIP⊗2B⊗\quad $v = 10↑9$ and W = U.)\cr
⊗⊗SLAX⊗5⊗rA → next nine digits.\cr
⊗⊗CHAR⊗⊗\cr
⊗⊗STA⊗BUF2,2(2:5(⊗Store next nine digits.\cr
⊗⊗STX⊗BUF2+1,2\cr
⊗⊗INC2⊗2⊗Increase buffer pointer.\cr
⊗⊗DEC3⊗1\cr
⊗⊗J3P⊗1B⊗Repeat ten times.\cr
⊗⊗OUT⊗BUF2??20,2(PRINTER)\cr
⊗⊗J2P⊗DONE⊗Have we printed both lines?\cr
⊗⊗ENT2⊗0⊗Set buffer pointer for 2nd buffer.\cr
⊗⊗JMP⊗8B\cr

\ansno 14. Let $K(n)$ be the number of steps
required to convert an $n$-digit decimal number to binary and
at the same time to compute the binary representation of 10$↑|εn$.
Then we have $K(2n) ≤ 2K(n) + O\biglp M(n)\bigrp . Proof{\sl
: }$Given the number $U = (u↓{2n-1} \ldotsm u↓0)↓{10}$, compute
$U↓1 = (u↓{2n-1} \ldotsm u↓n)↓{10}$ and $U↓0 = (u↓{n-1} \ldotsm
u↓0)↓{10}$ and 10$↑n$, in $2K(n)$ cycles, then compute $U =
10↑nU↓1 + U↓0$ and $10↑{2n} = 10↑n \cdot 10↑n$ in $O\biglp M(n)\bigrp$
cycles. It follows that $K(2↑n) = O\biglp M(2↑n) + 2M(2↑{n-1})
+ 4M(2↑{n-2}) + \cdotss\bigrp = O\biglp nM(n)\bigrp
$.
|qleft |newtype \qquad (Similarly, Sch|spose 4onhage has observed
that we can convert a (2$↑n$ lg$↓2 10)-bit number U$ from binary
to decimal, in $O\biglp nM(2↑n)\bigrp$ steps. First form $V
= 10↑2|supsup n|supsup -|supsup 1$ in $O\biglp M(2↑{n-1}) +
M(2↑{n-2}) + \cdotss\bigrp = O\biglp M(2↑n))$ steps,
then compute $U↓0 = (U$ mod $V)$ and $U↓1 = \lfloor U/V\rfloor$
in $O\biglp M(2↑n))$ further steps, then convert $U↓0$ and $U↓1.)$

\ansno 18. Let $U =$ round$↓B(u, P)$ and $v =$ round$↓b(U, p)$.
We may assume that $u ≠ 0$, so that $U ≠ 0$ and $v ≠ 0. Case
{\sl 1} v < u:$ Determine $e$ and $E$ such that $b↑{e-1} < u
≤ b↑e, B↑{E-1} ≤ U < B↑E$. Then $u ≤ b↑{p-e}u ≤ U + {1\over
2}B↑{E-P}$ and $U ≤ u - {1\over 2}b↑{e-p}$; hence $B↑{P-1} ≤
B↑{P-E}U < B↑{P-E}u ≤ b↑{p-e}u ≤ b↑p. Case {\sl 2}, v > u:$
Determine $e$ and $E$ such that $b↑{e-1} ≤ u < b↑e, B↑{E-1}
< U ≤ B↑E$. Then $u ≥ U - {1\over 2}B↑{E-P}$ and $U ≥ u + {1\over
2}b↑{e-p}$; hence $B↑{P-1} ≤ B↑{P-E}(U - B↑{E-P}) < B↑{P-E}u
≤ b↑{p-e}u < b↑p$. Thus we have proved that $B↑{P-1} < b↑p$
whenever $v ≠ u$.

Conversely, if $B↑{P-1} < b↑p$, the above proof
suggests that the most likely example for which $u ≠ v$ will
occur when $u$ is a power of $b$ and at the same time it is
close to a power of $B$. We have $B↑{P-1}b↑p < B↑{P-1}b↑p +
{1\over 2}b↑p - {1\over 2}B↑{P-1} - {1\over 4} = (B↑{P-1} +
{1\over 2}) \times (b↑p - {1\over 2})$; hence $1 < α = 1/(1
- {1\over 2}b↑{-p}) < 1 + {1\over 2}B↑{1-P} = β$. There are
integers $e$ and $E$ such that log$↓B α < e$ log$↓B b - E <$
log$↓B β$, since Weyl's theorem (exercise 3.5--22) implies that
there is an integer $e$ with $0 <$ log$↓B α < (e$ log$↓B)$mod
1 < log$↓B β < 1$ when log$↓B b$ is irrational. Hence $α < b↑e/B↑E
< β$, for some $e$ and $E$. (Such $e$ and $E$ may also be found
by applying the theory of continued fractions, see Section 4.5.3.)
Now we have round$↓B(b↑e, P) = B↑E$, and round$↓b(B↑E, p) <
b↑e. [{\sl CACM \bf 11} (1968), 47--50; {\sl Proc.\ Amer.\ Math.\ Soc.\
\bf 19} (1968), 716--723.]

\ansno 19. $m↓1 = (FOFOFOFO)↓{16}, c↓1 = 1 - 10/16$ makes $U
= \biglp (u↓7u↓6)↓{10} \ldotsm (u↓1u↓0)↓{10}\bigrp ↓{256}; m↓2
= (FFOOFFOO)↓{16}, c↓2 = 1 - 10↑2/16↑2$ makes $U = \biglp (u↓7u↓6u↓5u↓4)↓{10}(u↓3u↓2u↓1u↓0)↓{10}\bigrp
↓{65536}; m↓3 = (FFFFOOOO)↓{16}; c↓3 = 1 - 10↑4/16↑4$. (Cf.\
exercise 14. This technique is due to Roy A. Keir, circa 1958.)

%folio 769 galley 3b (C) Addison-Wesley 1978	-
|qleft \24skip |newtype {\:r SECTION 4.5.1

\ansno 1. Test whether or not $uv↑\prime
< u↑\prime v$, since the denominators are positive.

\ansno 2. If $c > 1$ divides both $u/d$ and $v/d$, then $cd$
divides both $u$ and $v$.

\ansno 3. Let $p$ be prime. If $p↑e$ is a divisor
of $uv$ and $u↑\prime v↑\prime$ for $e ≥ 1$, then either $p↑e\rslash
u$ and $p↑e\rslash v↑\prime$ or $p↑e\rslash u↑\prime$ and $p↑e\rslash
v$; hence $p↑e\rslash$ gcd($u, v↑\prime )$ gcd($u↑\prime , v)$.
The converse follows by reversing the argument.

\ansno 4. Let $d↓1 =$ gcd($u, v), d↓2 =$ gcd($u↑\prime , v↑\prime
)$; the answer is $w = (u/d↓1)(v↑\prime /d↓2)$ sign($v), w↑\prime
= |(u↑\prime /d↓2)(v/d↓1)|$, with a ``divide by zero'' error
message if $v = 0$.

\ansno 5. d$↓1 = 10, t = 17 \cdot 7 - 27 \cdot
12 = -205, d↓2 = 5, w = -41, w↑\prime = 168$.

\ansno 6. Let $u↑{\prime\prime} = u↑\prime /d↓1, v↑{\prime\prime}
= v↑\prime /d↓1$; we want to show that gcd($uv↑{\prime\prime} + u↑{\prime\prime}
v, d↓1) =$ gcd($uv↑{\prime\prime} + u↑{\prime\prime} v, d↓1u↑{\prime\prime} v↑{\prime\prime}
)$. If $p$ is a prime that divides $u↑{\prime\prime} $, then $p$ does
not divide $u$ or $v↑{\prime\prime} $, sp $p$ does not divide $uv↑{\prime\prime}
+ u↑{\prime\prime} v$. A similar argument holds for prime divisors of
$v↑{\prime\prime} $, so no prime divisors of $u↑{\prime\prime} v↑{\prime\prime}$ affect
the given gcd.

\ansno 7. $(N - 1)↑2 + (N - 2)↑2 = 2N↑2 - (6N - 5)$. If the
inputs are $n$-bit binary numbers, $2n + 1$ bits may be necessary
to represent $t$.

\ansno 8. For multiplication and division these quantities will
obey the rules $x/0 =$ sign($x)∞, (\pm ∞) \times x = x \times
(\pm ∞) = (\pm ∞)/x = \pm$ sign($x)∞, x/(\pm ∞) = 0$, provided
that $x$ is finite and nonzero, without change to the algorithms
described. Furthermore, the algorithms can readily be modified
so that 0/0 = 0 \times (\pm ∞) = (\pm ∞) \times 0 = ``(0/0)'',
where the latter is a representation of ``undefined''; and so
that if either operand is ``undefined'' the result will be ``undefined''
also. Since the multiplication and division subroutines can
yield these fairly natural rules of ``extended arithmetic,''
it is sometimes worth while to modify the addition and subtraction
operations so that they satisfy the rules $x \pm ∞ = \pm X,
x \pm (-∞) = \mp X$, for $x$ finite; (\pm ∞) + (\pm ∞) = \pm
∞ - (\mp ∞) = \pm ∞, (\pm ∞) + (\mp ∞) = (NX) - (\pm ∞) = (0/0);
and if either or both operands is (0/0), so is the result. Equality
tests and comparisons may be treated in a similar manner.

The above remarks are independent of ``overflow''
indications. If ∞ is being used to suggest overflow, it is incorrect
to let 1/X be equal to zero, or to let ∞ - ∞ be equal to zero,
lest inaccurate results be regarded as true answers! It is far
better to represent overflow by $(0/0)$, and to use the convention
that the result of any operation is undefined if at least one
of the inputs is undefined. This type of overflow indication
has the advantage that final results of an extended calculation
reveal exactly which answers are defined and which are not.

\ansno 9. If $u/u↑\prime |spose ??= v/v↑\prime $, then
$$$1 ≤ |uv↑\prime - u↑\prime v| = u↑\prime v↑\prime |(u/u↑\prime
) - (v/v↑\prime )| < |2↑{2n}(u/u↑\prime ) - 2↑{2n}(v/v↑\prime
)|$;
|qctr \9skip two quantities differing by more than unity cannot
have the same ``floor.'' \biglp In other words, the first $2n$
bits to the right of the binary point is enough to characterize
the value of the fraction, when there are $n$-bit denominators.
We cannot improve this to $2n - 1$ bits, for if $n = 4$ we have
${1\over 13}$ = (.00010011 . . .)$↓2, {1\over 14} = (.00010010
. . .)↓2.\bigrp$

 \ansno 11. To divide by $(v + v↑\prime \sqrt{5})/v↑{\prime\prime} $,
when $v$ and $v↑\prime$ are not both zero, multiply by|newtype
58320---Computer
%folio 770 galley 4 (C) Addison-Wesley 1978	-
Programming\quad (Knuth/A.-W.)\quad f. 770\quad ch. 4\quad g.
4c
$${\:r SECTION 4.5.2

\ansno 1. Substitute min, max, + consistently
for gcd, lcm, \times.

\ansno 2. For prime $p$, let $u↓p, v↓1|infinf p, \ldotss , v↓{np}$
be the exponents of $p$ in the canonical factorization of $u,
v↓1, \ldotss , v↓n$. By hypothesis, $u↓p ≤ v↓{1p} +\cdots
+ v↓{np}$. We must show that $u↓p ≤$ min($u↓p, v↓{1p})
+\cdots +$ min($u↓p, v↓{np})$, and this is certainly
true if $u↓p$ is greater than or equal to each $v↓{jp}$, or
if $u↓p$ is less than some $v↓{jp}$.

\ansno 3.} Solution {\sl 1: }A one-to-one correspondence
is obtained if we set $u =$ gcd($d, n), v = n↑2/$lcm($d, n)$
for each divisor $d$ of $n↑2. Solution {\sl 2: }$If $n = p↑{e}↓{1↑1}
\ldotss p↑{e}↓{r↑r}$, the number in each case is $(2e↓1 + 1)
\ldotsm (2e↓r + 1)$.

\ansno 4. See exercise 3.2.1.2--15(a).

\ansno 5. Shift $u, v$ right until neither is a
multiple of 3; each iteration sets $t ← u + v$ or $t ← u - v
($whichever is a multiple of 3), and shifts $t$ right until
it is not a multiple of 3, then replaces max$(u, v)$ by the
result.

|qleft \9skip |tab |tab |tab |tab |zfa ⊗$u⊗\qquad \qquad v⊗\qquad
\qquad t\cr
\3skip 13634⊗\qquad \qquad 24140⊗\qquad \qquad 10506, 3502;\cr
13636⊗\qquad \qquad 3502⊗\qquad \qquad 17136, 5712, 1904;\cr
1904⊗\qquad \qquad 3502⊗\qquad \qquad 5406, 1802;\cr
1904⊗\qquad \qquad 1802⊗\qquad \qquad 102, 34;\cr
34⊗\qquad \qquad 1802⊗\qquad \qquad 1836, 612, 204, 68;\cr
34⊗\qquad \qquad 68⊗\qquad \qquad 102, 34;\cr
34⊗\qquad \qquad 34⊗\qquad \qquad 0.\cr

\ansno 6. The probability that both $u$ and
$v$ are even is ${1\over 4}$; the probability that both are
multiples of four is ${1\over 16}$; etc. Thus $A$ has the distribution
given by the generating function
$$${3\over 4}$ + ${3\over 16}$$z + {3\over 64}z↑2 +\cdots
 = {{3\over 4}??21 - z/4?? $.
|qctr \9skip The mean is ${1\over 3}$, and the standard deviation
is \sqrt{${2\over 9}$ + ${1\over 3}$ - ${1\over 9}$ = ${2\over
3}$. If $u, v$ are independently and uniformly distributed with
$1 ≤ u, v < 2↑N$, then some small correction terms are needed;
the mean is then actually
$$$(2↑N - 1)↑{-2} \sum ↓{1≤k≤N(2↑{N-k} - 1)↑2 = {1\over 3} -
{4\over 3}(2↑N - 1)↑{-1} + N(2↑N - 1)↑{-2}$.

\ansno 7. When $u, v$ are not both even, each of
the cases (even, odd), (odd, even), (odd, odd) is equally probable,
and $B = 1, 0, 0$ in these cases. Hence $B = {1\over 3}$ on
the average. Actually, as in exercise 6, a small correction
could be given to be strictly accurate when $1 ≤ u, v < 2↑N$;
the probability that $B = 1$ is actually
$$$(2↑N - 1)↑{-2}\sum ↓{1≤k≤N}(2↑{N-k} - 1)2↑{N-k} = {1\over
3} - {1\over 3}(2↑N - 1)↑{-1}$.

\ansno 8. $E$ is the number of subtraction cycles
in which $u > v$, plus one if $u$ is odd after step B1. If we
change the inputs from $(u, v)$ to $(v, u)$, the value of $C$
stays unchanged, while $E$ becomes $C - E$ or $C - E - 1$; the
latter case occurs iff $u$ and $v$ are both odd after step B1,
and this has probability ${1\over 3}$ + ${2\over 3}$/(2$↑N -
1)$. Hence
$$$E$$↓{ave} = C$$↓{ave} - E$$↓{ave} - {1\over 3} - {2\over
3}/(2↑N - 1)$.

\ansno 9. The binary algorithm first gets to B6
with $u = 1963, v = 1359$; then $t ← 604, 302, 151$, etc. The
gcd is 302. Using Alforithm X we find that 2 \cdot 31408 - 23
\cdot 2718 = 302.

\ansno 10. (a) Two integers are relatively prime iff they are
not both divisible by any prime number.\xskip (b) Rearrangement of
the sum in (a), in terms of the denominators $k = p↓1 \ldotsm
p↓r$. $\biglp$Note
that each of the sums in (a), (b) is actually finite.$\bigrp$\xskip
(c) $(n/k)↑2 - \lfloor n/k\rfloor ↑2 = O(n/k)$, so $q↓n - \sum
↓{1≤k≤n} \mu (k)(n/k)↑2 = \sum ↓{1≤k≤n} O(n/k) = O(nH↓n)$.\xskip (d)
\sum ↓{$d\rslash n} \mu (d) = \delta ↓{1n}$. [In fact we have
the more general result
$$$\sum ↓{d\rslash n} \mu (d)\left({n\over d}}↑s = n↑s - \sum
\left({n\over p}}↑s +\cdotss$,
|qctr \9skip as in part (b), where the sums are over the prime
divisors of $n$, and this equals $n↑s(1 - 1/p↑{s}↓{1}) \ldotsm
(1 - 1/p↑{s}↓{r})$ if $n = p↑{e↓1}↓{1} \ldotss p↑{e↓r}↓{r}.]$

Notes{\sl : }This proof of Theorem D is due to
F. Mertens, {\sl J. f\"ur die reine und angew.\ Math.\ \bf 77}
(1874), 289--291. The technique gives a much stronger result,
namely that $6π↑{-2}n↑2 + O(n$ log $n)$ pairs of integers $u\in\biglp
f(n), f(n) + n\bigrp , v \in |newtype [|newtype g(n), g(n) +
n|newtype ) |newtype$ are relatively prime, for arbitrary $f$
and $g$. Similarly, a set of $k$ integers is relatively prime
with probability $1/(\sum ↓{n≥1} 1/n↑k)$.

\ansno 11. (a) 6/$π↑2$ times 1 + ${1\over 4}$ + ${1\over 9}$,
namely 49/6$π↑2 \approx .82746$.\xskip (b) 6/$π↑2$ times 1/1 + 2/4
+ 3/9 +\cdotss, namely $∞$. $\biglp$This is true in spite of the
result of exercise 12, and in spite of the fact that the average
value of ln gcd($u, v)$ is a small, finite number.$\bigrp$

\ansno 12. Let $\sigma (n)$ be the number
of positive divisors of $n$. The answer is
$$$\sum ↓{k≥1} \sigma (k) \cdot {6\over π↑2k↑2} = {6\over π↑2}
|newtype \left(|newtype \sum ↓{k≥1} {1\over k↑2}|newtype }|newtype
↑2 = {π↑2\over 6} $.
|qctr \9skip [Thus, the average is {\sl less} than 2, although
there are always at least two common divisors when $u, v$ are
not relatively prime.]

%folio 771 galley 5 (C) Addison-Wesley 1978	-
F. 772\quad ch. 4\quad g. 5c
\ansno 13. 1 + ${1\over 9}$ + ${1\over 25}$ +\cdots
= 1 + ${1\over 4}$ + ${1\over 9}$ +\cdots - ${1\over
4}$(1 + ${1\over 4}$ + ${1\over 9}$ +\cdot {\bf O O}).

\ansno 14. $v↓1 = \mp v/u↓3, v↓2 =M7O0\mp u/u↓3$ (the sign depends
on whether the number of iterations is even or odd). This follows
from the fact that $v↓1$ and $v↓2$ are relatively prime to each
other (throughout the algorithm), and that $v↓1u = -v↓2v$. [Hence
$v↓1u =$ lcm($u, v)$ at the close of the alforithm, but this
is not an especially efficient way to compute the least common
multiple. For a generalization, see exercise 4.6.1--18.]

G. E. Collins has observed that $|u| ≤ {1\over
2}v/u↓3, |u↓2| ≤ {1\over 2}u/u↓3$, at the termination of Algorithm
X\null, except in certain trivial cases, since the final value of
$q$ is usually ≥2. This bounds the size of $|u↓1|, |u↓2|$ throughout
the execution of the alforithm.

\ansno 15. Apply Algorithm X to $v$ and $m$, thus obtaining
a value $x$ such that $xv ≡ 1$ (modulo $m)$. (This can be done
by simplifying Algorithm X so that $u↓2$ and $v↓2$ are not computed,
since they are never used in the answer.) Then set $w ← ux$
mod $m$. [It follows, as in exercise 30, that this process requires
$O(n↑2)$ units of time, when it is applied to large $n$-bit
numbers.]
|qleft ??????|newtype 58320---Computer Programming\quad (Knuth/A.-W.)\quad
\ansno 16. (a) Set $t↓1 = x + 2y + 3z$; then $3t↓1 + y + 2z
= 1, 5t↓1 - 3y - 20z = 3$. Eliminate $y$, then $14t↓1 - 14z
= 6:$ No solution.\xskip (b) This time $14t↓1 - 14z = 0$. Divide by
14, eliminate $t↓1$; the general solution is $x = 8z - 2, y
= 1 - 5z, z$ arbitrary.

\ansno 17. Let $u↓1, u↓2, u↓3, v↓1, v↓2, v↓3$ be multiprecision
variables, not just $u$ and $v$. The extended algorithm will
act the same on $u↓3$ and $v↓3$ as Algorithm L does on $u$ and
$v$. New multiprecision operations are to set $t ← Au↓j, t ←
t + Bv↓j, w ← Cu↓j, w ← w + Dv↓j, u↓j ← t, v↓j ← w$ for all
$j$, in step L4; also if $B = 0$ in that step to set $t ← u↓j
- qv↓j, u↓j ← v↓j, v↓j ← t$ for all $j$ and for $q = \lfloor
u↓3/v↓3\rfloor $. A similar modification is made to step L1
if $v↓3$ is small. The inner loop (steps L2 and L3) is unchanged.

\ansno 18. If $mn = 0$, the probabilities of the lattice-point
model in the test are exact, so we may assume that $m ≥ n >
0. Valida vi$, the following values have been obtained:
$$\qquad {\sl Case {\sl 1}, m = n.} From $(n, n)$ we go to $(n
- t, n)$ with probability $t/2↑t - 5/2↑{t+1} + 3/2↑{2t}$, for
$2 ≤ t < n$. (These values are ${1\over 16}$, ${7\over 64}$,
${27\over 256}$, \ldotss\, .) To (0, $n)$ the probability is $n/2↑{n-1}
- 1/2↑n + 1/2↑{2n-2}$. To $(n, k)$ the probability is the same
as to $(k, n)$. The algorithm terminates with probability $1/2↑{n-1}$.

|qleft \3skip \qquad Case {\sl 2}, m = n + 1. From $(n + 1,
n)$ we get to $(n, n)$ with probability ${1\over 8}$ when $n
> 1$, or 0 when $n = 1$; to $(n - t, n)$ with probability 11/2$↑{t+3}
- 3/2↑{2t+1}$, for $1 ≤ t < n - 1$. (These values are ${5\over
16}$, ${1\over 4}$, \ldotss\,.) We get to (1, $n)$ with probability
$5/2↑{n+1} - 3/2↑{2n-1}$, for $n > 1$; to (0, $n)$ with probability
3/2$↑n - 1/2↑{2|}εn - 1/2↑{2n-1}$.

Case {\sl 3}, m ≥ n + 2. The probabilities are
given by the following table:
$$
|qctr ⊗(m - 1, n):⊗1/2 - 3/2$↑{m-n+2} - \delta ↓{n1}/2↑{m+1};\cr
⊗(m - t, n):⊗1/2↑t + 3/2↑{m-n+t+1}, 1 < t < n;\cr
⊗(m - n, n):⊗1/2↑n + 1/2↑m, n > 1;\cr
⊗(m - n - 1, n):⊗1/2↑{n+1} + 1/2↑{m-1};\cr
⊗(m - n - t, n):⊗1/2↑{n+t}, 1 < t < m - n;\cr
⊗(0, n):⊗1/2↑{m-1}.\cr
\6skip \qquad [Note{\sl : }$Although these exact probabilities
will certainly improve on the lattice-point model considered
in the text, they lead to recurrence relations of much greater
complexity; and they will not provide the true behavior of Algorithm
B\null, since for example the probability that gcd($u, v) = 5$ is
different from the probability that gcd($u, v) = 7.]$

|qleft \3skip
\ansno 19.
 |qleft \hfill A$↓{n+1} ⊗= a + \sum ↓{1≤k≤n} 2↑{-k}A↓{(n+1)(n-k)}
+ 2↑{-n}b\cr
\4skip ⊗= a + \sum ↓{1≤k≤n} 2↑{-k}A↓{n(n-k)} + {c\over 2} (1
- 2↑{-n}) + 2↑{-n}b\cr
\4skip ⊗= a + {1\over 2}A↓{n(n-1)} + {1\over 2}(A↓n - a) + {c\over
2} (1 - 2↑{-n});\cr
\6skip$ now substitute for $A↓{n(n-1)}$ from (36).

\ansno 20. The paths described in the hint have the same probability,
only the subsequent termination of the alforithm has a different
probability; thus $λ = k + 1$ with probability 2$↑{-k}$ times
the probability that $λ = 1$. Let the latter probability be
$p$. We know from the text that $λ = 0$ with approximate probability
${3\over 5}$; hence ${2\over 5}$ = $p(1 + {1\over 2} + {1\over
4} + {1\over 8} +\cdotss) = 2p$. The average is $p(1
+ {2\over 2} + {3\over 4} + {4\over 8} +\cdotss)
= p(1 + {1\over 2} + {1\over 4} + {1\over 8} +\cdotss
)↑2 = 4p$. [The exact probability that $λ = 1$ is ${1\over 5}$
- ${6\over 5}$($-{1\over 4}$)$↑n$ if $m > n ≥ 1, {1\over 5}
- {16\over 5}(-{1\over 4})↑n$ if $m = n ≥ 2.]$

\ansno 21. Show that for fixed $v$ and for $2↑m < u < 2↑{m+1}$,
when $m$ is large, each subtraction-shift cycle of the algorithm
reduces \lfloor lg$↓2 u\rfloor$ by two on the average.

\ansno 22. Exactly $(N - m)2↑{m-1+|}≤d|infsup m|infsup 0$ integers
$u$ in the range $1 ≤ u 2↑N$ have \lfloor lg$↓2 u\rfloor = m$
after $u$ has been shifted right until it is odd.

\ansno 23. The first sum is $2↑{2N-2} \sum ↓{0≤m<n<N} mn2↑{-m-n}\biglp
(α + β)N + \gamma - αm - βn\bigrp $. Since $\sum ↓{0≤m<n} m2↑{-m=2}
- (n+ 1)2↑{1-n}$ and $\sum ↓{0≤m<n} m(m - 1)2↑{-m} = 4 - (n↑2
+ n + 2)2↑{1-n}$, the sum on $m$ is $2↑{2N-2} \sum ↓{0≤n<N}
n2↑{-n}\biglp (\gamma - α + (α + β)N)(2 - (n + 1)2↑{1-n} - α(4
- (n↑2 + n + 2)2↑{1-n}) - βn\bigrp = 2↑{2N-2}\biglp (α + β)N
\sum ↓{0≤n<N} n2↑{-n}(2 - (n + 1)2↑{1-n}) + O(1)\bigrp $. Thus
the coefficient of $(α + β)N$ in the answer is found to be 2$↑{-2}\biglp
4 - ({4\over 3})↑3\bigrp = {11\over 27}. A similar argument
applies to the other sum$.

[{\sl Note{\sl : }}The {\sl exact} value of the
sums ay be obtained after some tedious calculation by means
of the general formula
$$$\sum ↓{0≤k<n}k↑mz↑k = {m!z↑m\over (1 - z)↑{m+1}} - \sum ↓{0≤k≤m}
{m↑kn↑{m-k}z↑{n+k}\over (1 - z)↑{k+1}}$
|qctr \6skip which follows from summation by parts.]

\ansno 24. Solving a recurrence similar to (34), we find
that the number of times is $A↓{mn}$, where $A↓{00} = 1, A↓{0n}
= (n + 3)/2, A↓{nn} = {8\over 5} - (3n + 13)/(9 \cdot 2↑n) +
{128\over 45}(-{1\over 4})↑n$ if $n ≥ 1, A↓{mn} = {16\over 15}(-{1\over
4})↑n$ if $m > n ≥ 1$. Since the condition $u = 1$ or $v = 1$
is therefore satisfied only about 1.6 times in an average run,
it is not worth making the suggested test each time step B5
is performed. (Of course the lattice model is not completely
accurate, but it seems reasonable to believe that it is not
too inaccurate for this application.)

\ansno 25. (a) $F↓{n+1}(x) = \sum ↓{d≥1}2↑{-d}$ Pr($X↓n < 1$
and $2↑d/(X↑{-1}↓{n} - 1) < x$ or $X↓n > 1$ and $(X↓n - 1)/2↑d
< x\bigrp = \sum ↓{d≥1} 2↑{-d}\biglp F↓n(1/(1 + 2↑dx↑{-1})\bigrp
+ F↓n(1 + 2↑dx) - F↓n(1)\bigrp $.\xskip (b) $G↓{n+1}(x) = 1 - \sum
↓{d≥1}2↑{-d}\biglp G↓n(1/(1 + 2↑dx)) - G↓n(1/(1 + 2↑dx↑{-1}))\bigrp
$.\xskip (c) $H↓n(x) = \sum ↓{d≥1}2↑{-d}$ Pr\biglp Y$↓n ≤ x and (1
- Y↓n)/2↑d ≤ x\bigrp = \sum ↓{d≥1} 2↑{-d}$ max\biglp 0, $G↓n(x)
- G↓n(1 - 2↑dx)\bigrp $.

Starting with $G↓0(x) = x$ we get rapid convergences
to a limiting distribution where \biglp G(.1), \ldotss , $G(.9)\bigrp
= (.2750, .4346, .5544, .6507, .7310, .7995, .8590, .9114, .9581)$.
The expected value of ln max($u↓n|infinf 1v↓n)/$max($u↓{n+1},
v↓{n+1})$ is \int ↑{1}↓{0}$ H↓n(t) dt/t$, and Brent has shown
that this can be written
$$\6skip \int ↑{1}↓{1/3} ${G↓n(t)\over t}$ dt - \int ↑{1/3}↓{0}
${G↓n(t)\over 1 - t}$ dt + \sum ↓{k≥1} 2$↑{-k}↑{1/(1+2↑k)}↓{1/(1+2↑{k+1})}
{G↓n(t)\over t(1 - t)} dt$.

\ansno 26. By induction, the length is
$m + \lfloor n/2\rfloor$ when $m ≥ n$, except that when $m =
n = 1$ there is $no$ path to (0, 0).
|qleft β?????????|newtype 5832
%folio 776 galley 6a (C) Addison-Wesley 1978	-
0---Computer Programming\quad (Knuth/A.-W.)\quad ch. 4\quad
f. 776\quad g. 6c
\ansno 27. Let $a↓n = \biglp 2↑n - (-1)↑n\bigrp /3$; then $a↓0,
a↓1, a↓2, \ldots = 0, 1, 1, 3, 5, 11, 21, . . $. (This sequence
of numbers has an interesting pattern of zeros and ones in its
binary representation. Note that $a↓n = a↓{n-1} + 2a↓{n-2}$,
and $a↓n + a↓{n+1} = 2↑n..)$ For $m > n$, let $u = 2↑{m+1} -
a↓{n+2}, v = a↓{n+2}$. For $m = n > 0$, let $u = a↓{n+2}, v
= 2a↓{n+1}$, or $u = 2a↓{n+1}, v = a↓{n+2}$ (depending on which
is larger). Another example for $m = n > 0$ is $u = 2↑{n+1}
- 1, v = 2↑{n+1} - 2$; this takes more shifts, and gives $C
= n + 1, D = 2n, E = 1$.

\ansno 28. This is a problem where it appears to be necessary
to prove {\sl more} than was asked just to prove what was asked.
Let us prove the following: {\sl If u, v are positive integers,
Algorithm B takes ≤1 + \lfloor} lg$↓2 max(u, v)\rfloor subtraction
cycles{\sl ; }and if equality holds, then \lfloor$ lg$↓2 (u
+ v)\rfloor > \lfloor$ lg$↓2 max(u, v)\rfloor $.

For convenience, let us assume that $u ≥ v$; let
$m = \lfloor$ lg$↓2 u\rfloor , n = \lfloor$ lg$↓2 v\rfloor $;
and let us use the ``lattice-point'' terminology, saying that
we are ``at point $(m, n).$'' The proof is by induction on $m
+ n$.

Case {\sl 1}, m = n. Clearly, \lfloor lg$↓2(u
+ v)\rfloor > \lfloor$ lg$↓2 u\rfloor$ in this case. If $u =
v$ the result is trivial; otherwise the next subtraction-shift
cycle takes us to a point $(m - k, m)$. By induction, at most
$m + 1$ further subtraction steps will be required; but if $m
+ 1$ more {\sl are} needed, we have \lfloor lg$↓2\biglp (u -
v)2↑{-r} + v\bigrp \rfloor > \lfloor$ lg$↓2 v\rfloor $, where
$r ≥ 1$ is the number of right shifts that were made. This is
impossible, since $(u - v)2↑{-r} + v < (u - v) + v = u$, so
at most $m$ further steps are needed.

{\sl Case {\sl 2}, m > n.} The next subtraction
step takes us to $(m - k, n)$, and at most 1 + max($m - k, n)
≤ m$ further steps will be required. Now if $m$ further steps
{\sl are} required, then $u$ has been replaced by $u↑\prime
= (u - v)2↑{-r}$ for some $r ≥ 1$. By induction, \lfloor lg$↓2(u↑\prime
+ v)\rfloor ≥ m$; hence
$$\lfloor lg$↓2(u + v)\rfloor = \lfloor$ lg$↓2 2\biglp (u -
v)/2 + v\bigrp \rfloor ≥ \lfloor$ lg$↓2 2(u↑\prime + v)\rfloor
≥ m + 1 > \lfloor$ lg$↓2 u\rfloor $.

\ansno 29. Subtract the $k$th column from the $2k$th,
$3k$th, $4k$th, etc., for $k = 1, 2, 3, \ldotss\,$. The result
is a triangular matrix with $x↓k$ on the diagonal in column
$k$, where $m = \sum ↓{d\rslash m} x↓d$. It follows that $x↓m
= \varphi (m)$, so the determinant is $\varphi (1)\varphi (2)
\ldotsm \varphi (n). [$In general, ``Smith's determinant,'' in
which the $(i, j)$ element is $f\biglp$ gcd($i, j)\bigrp$ for
an arbitrary function $f$, is equal to ??7↓{$1≤m≤n} \sum ↓{d\rslash
m} \mu (m/d)f(d)$, by the same argument. See L. E. Dickson,
{\sl History of the Theory of Numbers \bf 1} (New York: Chelsea,
1952), 122--123.]

\ansno 30. To determine $A$ and $r$ such that $u = Av + r, 0
≤ r < v$, using ordinary long division, takes $O\biglp (1 +$
log $A)($log $u)\bigrp$ units of time. If the quotients during
the algorithm are $A↓1, A↓2, \ldotss , A↓m$, then $A↓1A↓2 \ldotsm
A↓m ≤ u$, so log $A↓1 +\cdots +$ log $A↓m ≤$ log
$u$. Also $m = O($log $u)$.

\ansno 31. Since $(a↑u - 1)\mod (a↑v - 1) = a↑u$ $↑{mod} ↑v
- 1$ (cf.\ Eq.\ 4.3.2--19), we find that gcd($a↑m - 1, a↑n - 1)
= a↑{$gcd($m,n)} - 1$ for all positive integers $a$.

\ansno 32. Yes, to $O\biglp n($log $n)↑2($log
log $n)\bigrp $; see A. Sch|spose 4onhage, {\sl Acta Informatica
\bf 1} (1971), 139--144. [But Algorithm L is better in practice
unless $n$ is extremely large.]

\ansno 34. Keep track of the most significant and least significant
words of the operands (the most significant is used to guess
the sign of $t$ and the least significant is to determine the
amount of right shift), while building a 2 \times 2 matrix of
single-precision integers $A$ such that $A({u\atop v}) = ({u↑\prime
w\atop v↑\prime w})$ where $u↑\prime$ and $v↑\prime$ are smaller
than $u$ and $v$. (Instead of dividing the simulated odd operand
by 2, multiply the other one by 2, until obtaining multiples
of the word size $w$ after exactly lg $w$ shifts.) Experiments
show this algorithm running four times as fast as Algorithm
L.

%folio 777 galley 6b (C) Addison-Wesley 1978	-
\def\bslash{\char'477 } \def\vbslash{\char'477017 } % boldface slashes (vol. 2 only)
|qleft \3skip \24skip |newtype {\:r SECTION 4.5.3

\ansno 1. The running time is about
19.02$T + 6$, just a trifle slower than Program 4.5.2A.

\ansno 2. \left(${Q↓n(x↓1, \ldotss , x↓n)\over Q↓{n-1}(x↓2,
\ldotss , x↓n)}$\quad ${Q↓{n-1}(x↓1, \ldotss , x↓{n-1})\atop Q↓{n-2}(x↓2,
\ldotss , x↓{n-1})}$}.

\ansno 3. Q$↓n(x↓1, \ldotss , x↓n)$.

\ansno 4. By induction, or by taking the determinant
of the matrix product in exercise 2.

\ansno 5. When the $x$'s are positive, the $q$'s
of (9) are positive, and $q↓{n+1} > q↓{n-1}$; hence (9) is an
alternating series of decreasing terms, and it converges if
and only if $q↓n → ∞$. By induction, if the $x$'s are greater
than $ε, q↓n ≥ c(1 + ε/2)↑n$, where $c$ is chosen such that
$1 ≥ c, ε ≥ c(1 + ε/2)$. But if $x↓n = 1/2↑n$ then $q↓n ≤ 2
- 1/2↑n$.

\ansno 6. It suffices to prove that $A↓1 = B↓1$;
and from the fact that $0 ≤ \bslash x↓1, \ldotss , x↓n\bslash
< 1$ whenever $x↓1, \ldotss , x↓n$ are positive integers, we
have $B↓1 = \lfloor 1/X\rfloor = A↓1$.

\ansno 7. Only 1 2 \ldotsm $n$ and $n \ldotsm 2 1$.
(The variable $x↓k$ appears in exactly $F↓kF↓{n-k}$ terms; hence
$x↓1$ and $x↓n$ can only be permuted into $x↓1$ and $x↓n$. If
$x↓1$ and $x↓n$ are fixed by the permutation, it follows by
induction that $x↓2, \ldotss , x↓{n-1}$ are also fixed.)

\ansno 8. This is equivalent to
$$${Q↓{n-2}(A↓{n-1}, \ldotss , A↓2) - XQ↓{n-1}(A↓{n-1}, \ldotss
, A↓1)\over Q↓{n-1}(A↓n, \ldotss , A↓2) - XQ↓n(A↓n, \ldotss ,
A↓1)} = -{1\over X↓n} $,
|qctr \9skip and by (6) this is equivalent to
$$??????$X = {Q↓{n-1}(A↓2, \ldotss , A↓n) + X↓nQ↓{n-2}(A↓2, \ldotss
, A↓{n-1}\over Q↓n(A↓1, \ldotss , A↓n) + X↓nQ↓{n-1}(A↓1, \ldotss
, A↓{n-1})} $.

\ansno 9. (a) By definition.\xskip (b), (d) Prove this
when $n = 1$, then apply (a) to get the result for general $n$.\xskip
(c) Prove when $n = k + 1$, then apply (a).

\ansno 10. If $A↓0 > 0$, then $B↓0 = 0, B↓1 = A↓0, B↓2 = A↓1,
B↓3 = A↓2, B↓4 = A↓3, B↓5 = A↓4, m = 5$. If $A↓0 = 0$, then
$B↓0 = A↓1, B↓1 = A↓2, B↓2 = A↓3, B↓3 = A↓4, m = 3$. If $A↓0
= -1$ and $A↓1 = 1$, then $B↓0 = -(A↓2 + 2), B↓1 = 1, B↓2 =
A↓3 - 1, B↓3 = A↓4, m = 3$. If $A↓0 = -1$ and $A↓1 \bf Q} 1,
then $B↓0 = -2, B↓2 = A↓1 - 2, B↓3 = A↓2, B↓4 = A↓3, B↓5 = A↓4,
m = 5$. If $A↓0 < -1$, then $B↓0 = -1, B↓1 = 1, B↓2 = -A↓0 -
2, B↓3 = 1, B↓4 = A↓1 - 1, B↓5 = A↓2, B↓6 = A↓3, B↓7 = A↓4$.
[Actually, the last three cases involve eight subcases; if any
of the $B$'s is set to zero, the values should be ``collapsed
together'' by using the rule of exercise 9(c). For example,
if $A↓0 = -1, A↓1 = A↓3 = 1$, we actually have $B↓0 = -(A↓2
+ 2), B↓1 = A↓4 + 1, m = 1$. Double collapsing occurs when $A↓0
= -2, A↓1 = 1.]$
|qleft ????????????58320---Computer Programming\quad (Knuth/A.-W
%folio 777 galley 7 Bad beginning. (C) Addison-Wesley 1978	-
\def\bslash{\char'477 } \def\vbslash{\char'477017 } % boldface slashes (vol. 2 only)
.)\quad f. 777\quad ch. 4\quad g. 7c
\ansno 11. Let $q↓n = Q↓n(A↓1, \ldotss , A↓n), q↑\prime↓{n}
= Q↓n(B↓1, \ldotss , B↓n), p↓n = Q↓{n+1}(A↓0, \ldotss , A↓n),
p↑\prime↓{n} = Q↓{n+1}(B↓0, \ldotss , B↓n)$. We have $X =
(p↓m + p↓{m-1}X↓m)/(q↓m + q↓{m-1}X↓m), Y = (p↑\prime↓{n}
+ p↑\prime↓{n-1}Y↓n)/(q↑\prime↓{n} + q↑\prime↓{n-1}Y↓n)$;
therefore if $X↓m = Y↓n$, the stated relation between $X$ and
$Y$ holds by (8). conversely, if $X = (qY + r)/(sY + t), |qt
- rs| = 1$, we may assume that $s ≥ 0$, and we can show that
the partial quotients of $X$ and $Y$ eventually agree by induction
on $s$. The result is clear when $s = 0$, by exercise 9(d).
If $s > 0$, let $q = as + s↑\prime (0 ≤ s↑\prime < s)$. Then
$X = a + 1/\biglp (sY + t)/(s↑\prime Y + r - at)\bigrp $; since
$s(r - at) - ts↑\prime = sr - tq$, and $s↑\prime < s$, we know
by induction and exercise 10 that the partial quotients of $X$
and $Y$ eventually agree. [{\sl Note{\sl : }}The fact that $m$
is always odd in exercise 10 shows, by a close inspection of
this proof, thatBut by (12), $p↓{n-1}/q↓{n-1}/q↓{n-1}$ and $p↓n/q↓n$
are extremely close to $X$; since $X ≠ Y, Y - p↓n/q↓n$ and $Y
- p↓{n-1}/q↓{n-1}$ will have the same sign as $Y - X$ for all
large $n$. This proves that $Y↓n < 0$ for all large $n$; hence
0 < $X↓n < X↓n - Y↓n = 2\sqrt{D}/V↓n; V↓n$ must be positive.
Also $U↓n < \sqrt{D}$, since $X↓n > 0$. Hence $V↓n < 2\sqrt{\9skip
{-V↓{n+1}\over V↓n} = X↓nY↓n = {(q↓nX - p↓n)(q↓nY - p↓n)\over
(q↓{n-1}X - p↓{n-1})(q↓{n-1}Y - p↓{n-1})} $.
|qctr \9skip [A companion identity is
$$$Vp↓np↓{n-1} + U(p↓nq↓{n-1} + p↓{n-1}q↓n) + \biglp (U↑2 -
D)/V\bigrp q↓nq↓{n-1} = (-1)↑nU↓n.]$
|qctr \9skip \qquad (d) If $X↓n = X↓m$ for $n ≠ m$, then $X$
is an irrational number that satisfies the quadratic equation
$(q↓nX - p↓n)/(q↓{n-1}X - p↓{n-1} = (q↓mX - p↓m)/(q↓{m-1}X -
p↓{m-1})$.

\ansno 14. As in exercise 9, we need only verify the stated
identities when $c$ is the last partial quotient, and this verification
is trivial. Now Hurwitz's rule gives $2/e = \bslash ), 2, 1,
2, 0, 1, 1, 1, 1, 1, 0, 2, 3, 2, 0, 1, 1, 3, 1, 1, 0, 2, 5,
. . .\bslash $. Taking the receiprocal, collapsing out the
zeros as in exercise 9, and taking note of the pattern that
appears, we find that (cf.\ exercise 16) $e/2 = 1 + \bslash
2, 2m + 1, 3, 1, 2m + 1, 1, 3\bslash , m ≥ 0. [Schriften der
phys.-|spose 4okon.\ Gesellschaft zu K|spose 4onigsberg \bf 32}
(1891), 59--62.]

\ansno 15. \biglp This procedure maintains
four integers $(A, B, C, D)$ with the invariant meaning that
``our remaining job is to output the continued fraction for
$(Ay + B)/(Cy + D)$, where $y$ is the input yet to come.``\bigrp
Initially set $j ← k ← 0, (A, B, C, D) ← (a, b, c, d)$; then
input $x↓j$ and set $(A, B, C, D) ← (Ax↓j + B, A, Cx↓j + D,
C), j ← j + 1$, one or more times until $C + D$ has the same
sign as $C. \biglp$ When $j ≥ 1$ and the input has not terminated,
we know that $1 < y < ∞$; and when $C + D$ has the same sign
as $C$ we know therefore that $(Ay + B)/(Cy + D)$ lies between
$(A + B)/(C + D)$ and $A/C.\bigrp$ Now comes the general step:
If no integer lies strictly between $(A + B)/(C + D)$ and $A/C$,
output $X↓k ← \lfloor A/C\rfloor $, and set $(A, B, C, D) ←
(C, D, A - X↓kC, B - X↓kD), k ← k + 1$; otherwise input $x↓j$
and set $(A, B, C, D) ← (Ax↓j + B, A, Cx↓j + D, C), j ← j +
1$. The general step is repeated ad infinitum. However, if at
any time the $final x↓j$ is input, the algorithm immediately
switches gears: It outputs the continued fraction for $(Ax↓j
+ B)/(Cx↓j + D)$, using Euclid's algorithm, and terminates.

The following tableau shows the working for the
requested example, where the matrix $\left({b\quad A\atop D\quad
C}}$ begins at the upper left corner then shifts right one on
input, down one on output.

|qleft \12skip |tab \qquad \quad |tab \qquad \quad |tab \qquad
\quad |tab \qquad \quad |tab \qquad \quad |tab \qquad \quad
|tab \qquad \quad |tab \qquad \quad |tab \qquad \quad |tab \qquad
\quad |tab \qquad \quad |tab |zfa ⊗|linerule ⊗$x↓j⊗-1⊗5⊗1⊗1⊗1⊗2⊗1⊗2⊗∞\cr
\-2skip |linerule \quad X↓k:⊗ 39⊗ 97⊗ 58⊗ 193⊗⊗⊗⊗⊗⊗\cr
\quad -2⊗-25⊗-62⊗ 37⊗ 123\cr
\quad 2⊗⊗⊗ 16⊗ 53\cr
\quad 3⊗⊗⊗ 5⊗ 17⊗22⊗39\cr
\quad 7⊗⊗⊗ 1⊗ 2⊗ 3⊗ 5⊗8\cr
\quad 1⊗⊗⊗⊗⊗ 1⊗ 4⊗5⊗14\cr
\quad 1⊗⊗⊗⊗⊗⊗ 1⊗3⊗ 7\cr
\quad 1⊗⊗⊗⊗⊗⊗⊗2⊗ 7⊗9⊗25\cr
\quad 13⊗⊗⊗⊗⊗⊗⊗1⊗ 0⊗1⊗ 2\cr
\quad 2⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗ 1\cr
\quad ∞⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗ 0\cr
\12skip |newtype$ \qquad M. Mend|spose 2es France has shown
that the number of quotients output per quotient input is asymptotically
bounded between 1/$r$ and $r$, where $r = 2\lfloor K(|ad - bc|)/2\rfloor
+ 1$ and $K$ is the function defined in exercise 38; this bound
is best possible. {\sl [Colloquia Math. Soc. J|spose 1anos Bolyai},
Debrecen, 1974, to appear.]

The above algorithm can be generalized to compute
the continued traction for $(axy + bx + cy + d)/(Axy + Bx +
Cy + D)$ from those of $x$ and $y$ (in particular, to compute
sums an|newtype 58320---Computer Programming\quad (Knuth/A.-W.
%folio 781 galley 8 (C) Addison-Wesley 1978	-
\def\bslash{\char'477 } \def\vbslash{\char'477017 } % boldface slashes (vol. 2 only)
)\quad f. 781\quad ch. 4\quad g. 8c
\ansno 16. It is not difficult to prove by induction that $f↓n(z)
= z/(2n + 1) + O(z↑3)$ is an odd function with a convergent
power series in a neighborhood of the origin, and that it satisfies
the given differential equation. Hence
$$$f↓0(z) = \bslash z↑{-1} + f↓1(z)\bslash = \cdots = \bslash
z↑{-1}, 3z↑{-1}, \ldotss , (2n + 1)z↑{-1} + f↓{n+1}(z)\bslash
$.
|qctr \9skip It remains to prove that lim↓{$n→∞}\bslash z↑{-1},
3z↑{-1}, \ldotss , (2n + 1)z↑{-1}\bslash = f↓0(z)$. [Actually
Euler, age 24, obtained continued fraction expansions for the
considerably more general differential equation $f↑\prime↓{n}(z)
= az↑m + bf↓n(z)z↑{m-1} + cf↓n(z)↑2$; but he did not bother
to prove convergence, since formal manipulation and intuition
were good enough in the eighteenth century.]

There are several ways to prove the desired limiting
equation. First, letting $f↓n(z) = \sum ↓k a↓{nk}z↑k$, we can
argue from the equation
$$$\quad (2n + 1)a↓{n1} + (2n + 3)a↓{n3}z↑2 + (2n + 5)a↓{n5}z↑4
+\cdots$

|qleft  \4skip = 1 - (a$↓1z + a↓3z↑3 + a↓5z↑5 +\cdotss
)↑2\quad$
 |qright \9skip that (-1)$↑ka↓{n(2k+1)}$ is a sum of terms of
the form $c↓k/(2n + 1)↑{k+1}(2n + b↓{k1}) \ldotsm (2n + b↓{kk})$,
where the $c↓k$ and $b↓{km}$ are positive integers independent
of $n$. For example, $-a↓{n7} = 4/(2n + 1)↑4(2n + 3)(2n + 5)(2n
+ 7) + 1/(2n + 1)↑4(2n + 3)↑2(2n + 7)$. Thus $|a↓{(n+1)k}| ≤
|a↓{nk}|$, and $|f↓n(z)| ≤$ tan $|z|$ for $|z| < π/2$. This
uniform bound on $f↓n(z)$ makes the convergence proof very simple.
Careful study of this argument reveals that the power series
for $f↓n(z)$ actually converges for $|z| < π\sqrt{2n + 1}/2$;
this is interesting, since it shows that the singularities of
$f↓n(z)$ get farther and farther away from the origin as $n$
grows, so the continued fraction actually represents tanh {\sl
z throughout} the complex plane.

Another proof gives further information of a different
kind: If we let

Another proof gives further information of a different
kind: If we let
$$$A↓n(z) = n! \sum ↓{0≤k≤n} \left({2n - k\atop n}}z↑k\left/k!
= \sum ↓{k≥0} {(n + k)!z↑{n-k}\over k!(n - k)!} $,
|qctr \9skip then
$$$A↓{n+1}(z) = \sum ↓{k≥0} {(n + k - 1)!\biglp (4n + 2)k +
(n + 1 - k)(n - k)|newtype )\over |newtype k!(n + 1 - k)!} z↑$
{n+1-k}|qctr \4skip ????????????????????????????= (4n + 2)A$↓n(z)
+ z↑2A↓{n-1}(z)$.
|qctr \9skip It follows, by induction, that
$$$Q↓n\left({1\over z}, {3\over z} , \ldotss , {2n - 1\over z}}
|tab = {A↓n(2z) + A↓n(-2z)\over 2↑{n+1}z↑n} ,⊗\4skip \hfill
Q↓{n-1}\left({3\over z} , \ldotss , {2n - 1\over z}} ⊗= {A↓n(2z)
- A↓n(-2z)\over 2↑{n+1}z↑n} .\cr
\9skip$ Hence
|qleft $\bslash z↑{-1}, 3z↑{-1}, \ldotss , (2n - 1)z↑{-1}\bslash
= {A↓n(2z) - A↓n(-2z)\over A↓n(2z) + A↓n(-2z)} $,
|qctr \9skip and we want to show that this ratio approaches
tanh $z$. By Eqa. 1.2.9--11 and 1.2.6--26,
$$$e↑zA↓n(-z) = n! \sum ↓{m≥0} z↑m|newtype \left(|newtype \sum
↓{0≤k≤n} \left({m\atop k}}\left({2n - k\atop n}}(-1)↑k|newtype
}|newtype \sum ↓{m≥0} \left({2n - m\atop n}}z↑m {n!\over m!}
$.
|qctr \9skip Hence
$$$e↑zA↓n(-z) - A↓n(z) = R↓n(z) = (-1)↑nx↑{2n+1} \sum ↓{k≥0}
{(n + k)!x↑k\over (2n + k + 1)!k!} $.
|qctr \9skip |newtype We now have $(e↑{2z} - 1)\biglp A↓n(2z)
+ A↓n(-2z)\bigrp - (e↑{2z} + 1)\biglp A↓n(2z) - A↓n(-2z)\bigrp
= 2R↓n(2z)$; hence
$$|newtype $\bslash z↑{-1}, 3z↑{-1}, \ldotss , (2n - 1)z↑{-1}\bslash
= {2R↓n(2z)\over \biglp A↓n(2z) + A↓n(-2z)\bigrp (e↑{2z} + 1)}
$.
|qctr \9skip |newtype Thus we have an exact formula for the
difference. When $|z| ≤ {1\over 2}, e↑{2z} + 1$ is bounded away
from zero, $|R↓n(2z)| ≤ en!/(2n + 1)!$, and
$$${1\over 2}|A↓n(2z) + A↓n(-2z)| ≥ n!|newtype \left(|newtype
\left({2n\atop n}} - \left({2n - 2\atop n}} - \left({2n - 4\atop
n}} -\cdots |newtype }$
|qctr \4skip ≥ ${(2n)!\over n!}$ (1 - ${1\over 4}$ - ${1\over
16}$ -\cdotss) = ${2\over 3}$ ${(2n)!\over n!}$ .
|qctr \9skip |newtype Thus convergence is very rapid, even for
complex values of $z$.

To go from this continued fraction to the continued
fraction for $e↑z$, we have tanh $z = 1 - 2/(e↑{2z} + 1)$; hence
we get the continued fraction representation for $(e↑{2z} +
1)/2$ by simple manipulations. Hurwitz's rule gives the expansion
of $e↑{2z} + 1$, from which we may subtract unity. For $n$ odd,
|qleft \9skip $e↑{-2/n} = \bslash 1, 3mn + \lfloor n/2\rfloor
, (12m + 6)n, (3m + 2)n + \lfloor n/2\rfloor , 1\bslash ,\qquad
m ≥ 0$.
|qctr \qquad Another derivation has been given by C. S. Davis,
{\sl J. London Math.\ Soc.\ \bf 20} (1945), 194--198.

\ansno 17. (b) \bslash $x↓1 - 1, 1, x↓2
- 2, 1, x↓3 - 2, 1, \ldotss , 1, x↓{2n-1} - 2, 1, x↓{2n} - 1\bslash
$.

(c) 1 + \bslash 1, 1, 3, 1, 5, 1, . . .\bslash
.

\ansno 19. The sum for $1 ≤ k ≤ N$ is log$↓b \biglp 2 \cdot
3 \ldotsm (N + 1)\bigrp - log$↓b (1 \cdot 2 \ldotsm N) - log$↓b
\biglp (2 + x)(3 + x) \ldotsm (N + 1 + x)\bigrp +$ log$↓b \biglp
(1 + x)(2 + x) \ldotsm (N + x)\bigrp =$ log$↓b \biglp (1 + x)(N
+ 1)/(N + 1 + x)\bigrp $.

\ansno 20. Let $H = SG, g(x) = (1 + x)G↑\prime
(x), h(x) = (1 + x)H↑\prime (x)$. Then (35) implies that $h(x
+ 1)/(x + 2) - h(x)/(x + 1) = -(1 + x)↑{-2}g(1/(1 + )\bigrp
/\biglp 1 + 1/(1 + x)\bigrp $.

\ansno 21. $\varphi (x) = c/(cx + 1)↑2 + (2 - c)/\biglp (c -
1)x + 1\bigrp ↑2, U\varphi (x) = 1/(x + c)↑2$. When $c ≤ 1$,
the minimum of $\varphi (x)/U\varphi (x)$ occurs at $x = 0$
and is $2c↑2 ≤ 2$. When $c ≥ \phi = {1\over 2}(\sqrt{5} + 1)$,
the minimum occurs at $x = 1$ and is ≤$\phi ↑2$. When $c \approx
1.31266$ the values at $x = 0$ and $x = 1$ are nearly equal
and the minimum is >3.2; the bounds (0.29)$↑n\varphi ≤ U↑n\varphi
≤ (0.31)↑n\varphi$ are obtained. Still bounds come from well-chosen
linear combinations $Tg(x) = \sum a↓j/(x + c↓j)$.

\ansno 23. By the interpolation formula of exercise 4.64--15
with $x↓0 = 0, x↓1 = x, x↓2 = x + ε$, letting $ε → 0$, we have
the general identity $R↑\prime↓{n}(x) = \biglp R↓n(x) - R↓n(0)|newtype
)}h9}/x + {1\over 2}xR↓n\biglp \theta (x)\bigrp$ for some $\theta
(x)$ between 0 and $x$, whenever $R↓n$ is a function with continuous
second derivative. Hence in this case $R↑\prime↓{n}(x) =
O(2↑{-n})$.

\ansno 24. ∞. [A. Khinchin, in {\sl Compos.\ Math.\ \bf 1} (1935),
361--382, proved that the sum $A↓1 +\cdots + A↓n$
of the first $n$ partial quotients of a real number $X$ will
be asymptotically $n$ lg $n$, for almost all $X.]$
|qleft β????????????|newtype 58320---Computer
%folio 784 galley 9 (C) Addison-Wesley 1978	-
\def\bslash{\char'477 } \def\vbslash{\char'477017 } % boldface slashes (vol. 2 only)
Programming\quad (Knuth/A.-W.)\quad f. 784\quad ch. 4\quad g.
9c
\ansno 25. Any union of intervals can be written as a union
of disjoint intervals, since $∪↓{k≥1} I↓k = ∪↓{k≥1} (I↓k - ∪↓{1≤j<k}
I↓j)$, and this is a disjoint union in which $I↓k - ∪↓{1≤j<k}
I↓j$ can be expressed as a finite union of disjoint intervals.
Therefore we may take $??I = ∪ I↓k$, where $I↓k$ is an interval
of length $ε/2↑k$ containing the $k$th rational number in [0,
1], using some enumeration of the rationals. In this case $\mu
(??I- ≤ ε$, but \parallel $??I ∪ P↓n\parallel = n$ for all $n$.

\ansno 26. The continued fractions \bslash $A↓1, \ldotss , A↓t\bslash$
that appear are precisely those for which $A↓1 > 1, A↓t > 1$,
and $Q↓t(A↓1, A↓2, \ldotss , A↓t)$ is a divisor of $n$. Therefore
(6) completes the proof. \biglp {\sl Note{\sl :}} If $m↓1/n
= \bslash A↓1, \ldotss , A↓t\bslash$ and $m↓2/n = \bslash
A↓t, \ldotss , A↓1\bslash $, where $m↓1$ and $m↓2$ are relatively
prime to $n$, then $m↓1m↓2 ≡ \pm 1\modulo n$; this rule
defines the correspondence. When $A↓1 = 1$ an analogous symmetry
is valid, according to (38).\bigrp

\ansno 27. First prove the result for
$n = p↑e$, then for $n = rs$, where $r$ and $s$ are relatively
prime. alternatively, use the formulas in the next exercise.

\ansno 28. (a) The left-hand side is multiplicative
(see exercise 1.2.4--31), and it is easily evaluated when $n$
is a power of a prime.\xskip (c) From (a), we have $M|spose 4obius
inversion formula{\sl : }$If $f(n) = \sum ↓{d\rslash n} g(d)$,
then $g(n) = \sum ↓{d\rslash n} \mu (n/d)f(d)$.

\ansno 29. The sum is approximately (12 ln 2/$π↑2)$ ln $N!/N
- \sum ↓{d≥1} {\sl ??}(d)/d↑2 + 1.47$; here $\sum ↓{d≥1} {\sl
??}(d)/d↑2$ converges to the constant value $-\zeta ↑\prime
(2)/\zeta (2)$, while ln $N! = N$ ln $N - N + O($log $N)$ by
Stirling's approximation.

\ansno 30. The modified algorithm affects the calculation if
and only if the following division step in the unmodified algorithm
would have the quotient 1, and in this case it avoids the following
division step. The probability that a given division step is
avoided is the probability that $A↓k = 1$ and that this quotient
is preceded by an even number of quotients equal to 1. By the
symmetry condition, this is the probability that $A↓k = 1$ and
is {\sl followed} by an even number of quotients equal to 1.
The latter happens if and only if $X↓{k-1} > \phi - 1 = 0.618
\ldotss $, where $\phi$ is the golden ratio: For $A↓k = 1, A↓{k+1}
>$ iff ${2\over 3}$ ≤ $X↓{k-1} < 1; A↓k = A↓{k+1} = A↓{k+2}
= 1, A↓{k+3} > 1$ iff ${5\over 8}$ ≤ $X↓{k-1} < {2\over 3}$;
etc. Thus we save approximately $F↓{k-1}(1) - F↓{k-1}(\phi -
1) \approx 1 - lg$↓2 \phi \approx 0.306$ of the division steps.
The average number of steps is approximately (12 ln $\phi /π↑2)$ln
$n$, when $v = n$ and $u$ is relatively prime to $n$. Kronecker
[{\sl Vorlesungen |spose 4uber Zahlentheorie \bf 1} (Leipzig:
Teubner, 1901), 118] observed that this choice of least remainder
in absolute value always gives the shortest possible number
of iterations, over all algorithms that replace $u$ by $(\pm
u)$mod $v$ at each iteration. For further results see N. G.
de Bruijn and W. M. Zaring, {\sl Nieuw Archief voor Wiskunde
(3) \bf 1} (1953), 105--112.

On many computers, the modified algorithm makes
each division step longer; the idea of exercise 1, which saves
{\sl all} division steps when the quotient is unity, would be
preferable in such cases.

\ansno 31. Let $a↓0 = 0, a↓1 = 1, a↓{n+1} = 2a↓n + a↓{n-1}$;
then $a↓n = \biglp (1 + \sqrt{2})↑n - (1 - \sqrt{2})↑n\bigrp
/2\sqrt{2}$, and the worst case (in the sense of Theorem F)
occurs when $u = a↓n + a↓{n-1}, v = a↓n, n ≥ 2$.

This result is due to A. Dupr|spose fie [{\sl
J. de Math.\ \bf 11} (1846), 41--64], who also investigated more
general ``look-ahead'' procedures suggested by J. Binet. See
P. Bachmann, {\sl Niedere Zahlentheorie \bf 1} (Leipzig: Teubner,
1902), 99--118, for a discussion of early analyses of Euclid's
algorithm.

\ansno 32. $Q↓{m-1}(x↓1, \ldotss , x↓{m-1})Q↓{n-1}(x↓{m+2}, \ldotss
, x↓{m+n})$ corresponds to Morse code sequence of length $(m
+ n)$ in which a dash occupies positions $m$ and $(m + 1)$;
the other term corresponds to the opposite case. (Alternatively,
use exercise 2. Actually Euler gave the more general identity
$Q↓{m+n}(x↓1, \ldotss , x↓{m+n})Q↓k(x↓{m+1}, \ldotss , x↓{m+k})
= Q↓{m+k}(x↓1, \ldotss , x↓{m+k})Q↓n(x↓{m+1}, \ldotss , x↓{m+n})
+ (-1)↑kQ↓{m-1}(x↓1, \ldotss , x↓{m-1})Q↓{n-k-1}(x↓{m+k+z}, \ldotss
, x↓{m+n}).\bigrp$

 \ansno 33. (a) The new representations are $x = m/d, y = (n
- m)/d, x↑\prime = y↑\prime = d =$ gcd($m, n - m)$, for ${1\over
2}$$n < m < n$.\xskip (b) The relation $(n/x↑\prime ) - y ≤ x < n/x↑\prime$
defines $x$.\xskip (c) Count the $x↑\prime$ satisfying (b).\xskip (d) A
pair of integers $x > y > 0$, gcd($x, y = 1)$, can be uniquely
written in the form $x = Q↓m(x↓1, \ldotss , x↓m), y = Q↓{m-1}(x↓1,
\ldotss , x↓{m-1})$, where $x↓1 ≥ 2, m ≥ 1$; here $y/x = \bslash
x↓m, \ldotss , x↓1\bslash $.\xskip (e) It suffices to show that $\sum
↓{1≤k≤n/2}T(k, n) = 2\lfloor n/2\rfloor + h(n)$. For $1 ≤ k
≤ n/2$ the continued fractions $k/n = \bslash x↓1, \ldotss ,
x↓m)\rslash n$; and $T(k, n) = 2 + (m - 1)$.

\ansno 34. (a) Dividing $x, y$ by gcd($x,
y)$ yields $g(n) = \sum ↓{d\rslash n} h(n/d)$; apply exercise
28(c), and use the symmetry between primed and unprimed variables.\xskip
(b) For fixed $y$ and $t$ the representations with $xd ≥ x↑\prime$
have $x↑\prime < \sqrt{nd}$; hence there are $O(\sqrt{nd}/y)$
such representations. Now sum for $0 < t ≤ y < \sqrt{n/d}$.\xskip
(c) If $s(y)$ is the given sum, then $\sum ↓{d\rslash y} s(d)
= y(H↓{2y} - H↓y) = k(y)$, say; hence $s(y) = \sum ↓{d\rslash
y} k(y/d)$. Now $k(y) = y$ ln 2 - ${1\over 4}$ + $O(1/y)$.\xskip (d)
$\sum ↓{1≤y≤n} \varphi (y)/y↑2 = \sum ↓{1≤y≤n,d\rslash y} \mu
(d)/yd = \sum ↓{cd≤n} \mu (d)/cd↑2$. (Similarly, $\sum ↓{1≤y≤n}
\sigma ↓{-1}(y)/y↑2 = O(1).\bigrp$\xskip (e) $\sum ↓{1≤k≤n} \mu (k)/k↑2
= 6/π↑2 + O(1/n)$ (see exercise 4.5.2--10d); and $\sum ↓{1≤k≤n}
\mu (k)$log $k/k↑2 = O(1)$. Hence $h↓d(n) = n(3$ ln 2/$π↑2)$
ln$(n/d) + O(n)$ for $d ≥ 1$. So $h(n) = 2 \sum ↓{cd\rslash
n} \mu (d)h↓c(n/cd) = \biglp (6$ ln 2)/$π↑2\bigrp n($ln $n -
\sum - \sum ↑\prime ) + O(n\sigma ↓{-1}(n)↑2\bigrp $, where
$\sum = \sum ↓{cd\rslash n} \mu (d)$ln($cd)/cd = 0$ and $\sum
↑\prime = \sum ↓{cd\rslash n} \mu (d)$ln $c/cd = \sum ↓{d\rslash
n} {\sl ??}(d)/d$. [It is well known that $\sigma ↓{-1}(n) =
O($log log $n)$; cf.\ Hardy and Wright, {\sl Theory of Numbers,
+22.9.]}

\ansno 35. See ``Analysis of a subtractive algorithm,'' to appear.

\ansno 36. Working the algorithm backwards, we
want to choose $k↓1, \ldotss , k↓{n-1}$ so that $u↓k ≡ F↓k|infinf
1 \ldotsm F↓k|infinf i|infinf -|infinf 1F↓k|infinf i↓{-1} \biglp$
modulo gcd($u↓{i+1}, \ldotss , u↓n\bigrp$ for $1 ≤ < n$, with
$u↓n = F↓k|infinf 1 \ldotsm F↓k|infinf n|infinf -|infinf 1$ a
minimum, where the $k$'s are positive, $k↓1 ≥ 3$, and $k↓1 +\cdots
+ k↓{n-1} = N + n - 1$. The solution is $k↓2 =\cdots
= k↓{n-1} = 2, u↓n = F↓{N-n+3}. [$See {\sl CACM
\bf 13} (1970), 433--436, 447--448.]

\ansno 37. See {\sl Proc.\ Amer.\ Math.\
Soc.\ \bf 7} (1956), 1014--1021; cf.\ exercise 6.1--18.

\ansno 38. Let $m = \lceil n/\phi \rceil $, so that $m/n = \phi
↑{-1} + ε = \bslash x↓1, x↓2, \ldotss \bslash$ where $0 < ε
< 1/n$. Let $k$ be minimal such that $x↓k = 2$; then \biglp
$\phi ↑{1-k} + (-1)↑kF↓{k-1}ε\bigrp /\biglp \phi ↑{-k} - (-1)↑kF↓kε\bigrp
≥ 2$, hence $k$ is even and $\phi ↑{-2} = 2 - \phi ≤ \phi ↑kF↓{k+2}ε
= (\phi ↑{2k+2} - \phi ↑{-2})ε/\sqrt{5}. [Ann.\ Polon.\ Math.\
\bf 1} (1954), 203--206.]

\ansno 39. At least 287 at bats; \bslash
2, 1, 95\bslash = 96/287 = .33449477 \ldotsm$, and no fraction
with denominator <287 lies in [.3335, .3345] = [\bslash 2,
1, 666\bslash , \bslash 2, 1, 94, 1, 1, 3\bslash ].

To solve the general question of the fraction
in [9$a, b]$ with smallest denominator, where $0 < a < b < 1$,
note that in terms of regular continued fraction representations
we have $\bslash x↓1, x↓2, . . .\bslash < \bslash y↓1, y↓2,
. . .\bslash$ iff $(-1)↑jy↓j$ for the smmallest $j$ with $x↓j
≠ y↓j$, where we place ``∞'' after the last partial quotient
of a rational number. Thus if $a = \bslash x↓1, x↓2, . . .\bslash$
and $b = \bslash y↓1, y↓2, . . .\bslash $, the fractions in
$[a, b]$ have the form $c = \bslash x↓1, \ldotss , x↓{j-1},
z↓j, \ldotss , z↓m\bslash$ where $\bslash z↓j, \ldotss , z↓m\bslash$
lies between $\bslash x↓j, x↓{j+1}, . . .\bslash$ and $\bslash
y↓j, y↓{j+1}, . . .\bslash$ inclusive. Let $Q↓{-1} = 0$. The
denominator $Q↓{j-1}(x↓1, \ldotss , x↓{j-1})Q↓{m-j+1}(z↓j, \ldotss
, z↓m) + Q↓{j-2}(x↓1, \ldotss , x↓{j-2})Q↓{m-j}(z↓{j+1}, \ldotss
, z↓m)$ of $c$ is minimized when $m = j$ and $z↓j = (j$ odd
\dblrtarrow $y↓j + 1 - \delta ↓y|infinf j|infinf +|infinf 1↓∞;
x↓j + 1 - \delta ↓x|infinf j|infinf +|infinf 1↓∞)$.
|qleft
%folio 790 galley 10 (C) Addison-Wesley 1978	-
|newtype 58320---Computer Programming(Knuth/A.-W.)\quad f. 790\quad
ch. 4\quad g. 10c
$$|newtype {\:r SECTION 4.5.4

\ansno 1. If $d↓k$ isn't prime, its
prime factors are cost out before $d↓k$ is tried.

\ansno 2. No, the alforithm would fail if $p↓{t-1} = p↓t$, giving
``1'' as a spurious prime factor.

\ansno 3. Let $P$ be the product of the first 168 primes. ({\sl
Note{\sl :} }Although $P$ is a large number, it is considerably
faster on many computers to calculate this gcd than to do the
168 divisions, if we just want to test whether or not $n$ is
prime.)

\ansno 4. Cf.\ exercise 3.1--11 and Eq.\ 4.5.3--21;
the average is asymptotically $π↑2/12$ times the average value
of $\mu + λ$, since $n = λ\delta ↓|≤m↓0 + \mu + λ - 1 - \biglp
(\mu + λ - 1)$mod $λ\bigrp $.

\ansno 5. x mod 3 = 0; $x$ mod 5 = 0,
1, 4; $x$ mod 7 = 0, 1, 6; $x$ mod 8 = 1, 3, 5, 7; $x > 103$.
The first try is $x = 105: (105)↑2 - 10541 = 484 = 22↑2$. This
would also have been found by Algorithm C in a relatively short
time. Thus 10541 = 83 \cdot 127.

\ansno 6. Let us count the number of solutions
$(x, y)$ of the congruence $N ≡ (x - y)(x + y)\modulo p$,
where $0 ≤ x, y < p$. Since $N |spose ??≡ 0$ and $p$ is prime,
$x + y |spose ??≡ 0$. For each $v |spose ??≡ 0$ there is a unique
$u\modulo p$ such that $N ≡ uv$. The congruences $x - y
≡ u, x + y ≡ v$ now uniquely determine $x$ mod $p$ and $y$ mod
$p$, since $p$ is odd. Thus the stated congruence has exactly
$p - 1$ solutions $(x, y)$. If $(x, y)$ is a solution, so is
$(x, p - y)$ if $y ≠ 0$, since $(p - y)↑2 ≡ y↑2$; and if $(x,
y↓1)$ and $(x, y↓2)$ are solutions with $y↓1 ≠ y↓2$, we have
$y↑{2}↓{1} ≡ y↑{2}↓{2}$; hence $y↓1 = p - y↓2$. Thus the number
of different $x$ values among the solutions $(x, y)$ is $(p
- 1)/2$ if $N ≡ x↑2$ has no solutions, or $(p + 1)/2$ if $N
≡ x↑2$ has solutions.

\ansno 7. One procedure is to keep two indices for each modulus,
one for the current word position and one for the current bit
position; loading two words of the table and doing an indexed
shift command will bring the table entries into proper alignment.

\ansno 8. (We may assume that $N = 2M$
is even.) The following algorithm uses an auxiliary table $X[1],
X[2], \ldotss , X[M]$, where {\sl X[k]} represents the primality
of $2k + 1$.

|qleft \3skip |hangindent3\qquad {\bf S1.} Set {\sl X[k] ← 1}
for $1 ≤ k ≤ M$. Also set $j ← 1, p ← 1, p ← 3, q ← 4$. (During
this algorithm $p = 2j + 1, q = 2j + 2j↑2$; the integer variables
$j, k, p, q$ may readily be manipulated in index registers.)

|qleft \3skip \qquad {\bf S2.} If {\sl X[j] = 0}, go to S4.
Otherwise output $p$, which is prime, and set $k ← q$.

|qleft \3skip \qquad {\bf S3.} If $k ≤ M$, then set {\sl X[k]
← 0, k ← k + p}, and repeat this step.

|qleft \3skip \qquad {\bf S4.} Set $j ← j + 1, p ← p + 2, q
← q + 2p - 2$. If $j ≤ M$, return to S2.

|qleft \3skip |cancelindent |newtype A major part of this calculation
could be made noticeably faster if $q$ (instead of $j$) were
tested against $M$ in step S4, and if a new loop were appended
that outputs $2j + 1$ for all remaining {\sl X[j]} that equal
1, suppressing the manipulation of $p$ and $q$.

\ansno 9. If $p↑2$ is a divisor of $n$ for some
prime $p$, then $p$ is a divisor of $λ(n)$, but not of $n -
1$. If $n = p↓1p↓2$, where $p↓1 < p↓2$ are primes, then $p↓2
- 1$ is a divisor of $λ(n)$ and therefore $p↓1p↓2 - 1 ≡ 0 \biglp$
modulo$ (p↓2 - 1)\bigrp $. Since $p↓2 ≡ 1, p↓1 - 1$ is a multiple
of $p↓2 - 1$; but this contradicts $p↓1 < p↓2. \biglp$ Values
of $n$ for which $λ(n)$ properly divides $n - 1$ are called
``Carmichael numbers.'' See D. Shanks, {\sl Solved and Unsolved
Problems in Number Theory \bf 1} (Washington, D.C.: Spartan,
1962), Sections 39--40.\bigrp

 \ansno 10. Let $k↓p$ be the order of $x↓p$ modulo $n$, and let
$λ$ be the least common multiple of all the $k↓p$'s. Then $λ$
is a divisor of $n - 1$ but not of any $(n - 1)/p$, so $λ =
n - 1$. Since $x↑{\varphi (n)}↓{p}$ mod $n = 1, \varphi (n)$
is a multiple of $k↓p$ for all $p$, so $\varphi (n) ≥ λ$. But
$\varphi (n) < n - 1$ when $n$ is not prime. (Another way to
carry out the proof is to construct an element $x$ of order
$n - 1$ from the $x↓p$'s, by the method of exercise 3.2.1.2--15.)

\ansno 11. ⊗$U⊗V⊗A⊗P⊗S⊗T⊗$Output\cr
\3skip 1984 ⊗1 ⊗0 ⊗992 ⊗0 ⊗--- ⊗\cr
1981 ⊗1981 ⊗1 ⊗992 ⊗1 ⊗1981 ⊗\cr
1983 ⊗4 ⊗495 ⊗993 ⊗0 ⊗1 ⊗993$↑2 ≡ 2↑2 \cr
1983 ⊗991 ⊗2 ⊗98109 ⊗1 ⊗\cr
1981 ⊗4 ⊗495 ⊗2 ⊗0 ⊗1 ⊗2↑2 ≡ 2↑2 \cr
1984 ⊗1981 ⊗1 ⊗99099 ⊗1 ⊗1981 ⊗\cr
1984 ⊗1 ⊗1984 ⊗99101 ⊗0 ⊗1 ⊗99101↑2 ≡ 2↑0 \cr
\7skip |newtype The factorization 199 \cdot 991 is evident from
the first or last outputs. The shortness of the cycle, and the
appearance of the well-known number 1984, are probably just
coincidences$.

\ansno 12. The following algorithm makes use of an auxiliary
$(m + 1) \times (m + 1)$ matrix of single-precision integers
$E↓{jk}, 0 ≤ j, k ≤ m$; a single-precision vector $(b↓0, b↓1,
\ldotss , b↓m)$; and a multiple-precision vector $(x↓0, x↓1,
\ldotss , x↓m)$ with entries in the range $0 ≤ x↓k < N$.

\algstep F1. [Initialize.] Set
$b↓i ← -1$ for $0 ≤ i ≤ m$; then set $j ← 0$.

\algstep F2. [Next solution.] Get the next output
($x, e↓0, e↓1, \ldotss , e↓m$ produced by Algorithm E\null. (It is
convenient to regard Algorithms E and F as coroutines.) Set
$k ← 0$.

\algstep F3. [Search for odd.] If $k > m$ go to step
F5. Otherwise if $e↓k$ is even, set $k ← k + 1$ and repeat this
step.

\algstep F4. [Linear dependence?] If $b↓k ≥ 0$, then
set $i ← b↓k, x ← (x↓ix)$mod $N, e↓r ← e↓r + E↓{ir}$ for $0
≤ r ≤ m$; set $k ← k + 1$ and return to F3. Otherwise set $b↓k
← j, x↓j ← x, E↓{jr} ← e↓r$ for $0 ≤ r ≤ m$; set $j ← j + 1$
and return to F2. (In the latter case we have a new linearly
independent solution, modulo 2, whose first odd component is
$e↓k.)$

\algstep F5. [Try to factor.] (Now $e↓0, e↓1, \ldotss
, e↓m$ are even.) Set
$$$y ← \biglp (-1) ↑e|infsup 0↑{/2}p↑{e↓1/2}↓{1} \ldotss p↑{e↓m/2}↓{m}\bigrp$
mod $N$.
|qctr \7skip \qquad \qquad If $x = y$ or if $x + y = N$, return
to F2. Otherwise compute gcd($x - y, N)$, which is a proper
factor of $N$, and terminate the algorithm.

|qleft \3skip |cancelindent |newtype It can be shown that this
algorithm finds a factor, whenever one is deducible from the
given outputs of Algorithm E.

\ansno 13. $f(p, p↑2d) = 2/(p + 1) + f(p, d)/p$, since $1/(p
+ 1)$ is the probability that $A$ is a multiple of {\sl p. f(p,
pd) = 1/(p + 1)} when $d$ mod $p ≠ 0. f(2, 4k + 3) = {1\over
3}$ since $A↑2 - (4k + 3)B↑2$ cannot be a multiple of 4; $f(2,
8k + 5) = {2\over 3}$ since $A↑2 - (8k + 5)B↑2$ cannot be a
multiple of 8; $f(2, 8k + 1) = {1\over 3} + {1\over 3} + {1\over
3} + {1\over 6} + {1\over 12} +\cdots = {4\over 3}.
f(p, d) = (2p/(p↑2 - 1), 0\bigrp$ if $d↑{(p-1)/2}$ mod $p =
(1, p - 1)$, respectively, for odd $p$.

\ansno 14. Since $P↑2 ≡ kNQ↑2\modulo p$ for any prime divisor
$p$ of $V$, we have 1 ≡ $P↑{2(p-1)/2} ≡ (kNQ↑2)↑{(p-1)/2} ≡
(kN)↑{(p-1)/2}\modulo p$, if $P |spose ??≡ 0$.
|qleft ?????????|newtype 58320---Compu
%folio 794 galley 11a (C) Addison-Wesley 1978	-
ter Programming\quad (Knuth/A.-W.)\quad f. 794\quad ch. 4\quad
g. 11c
\ansno 15. $U↓n = (a↑n - b↑n)/\sqrt{D}$, where $a = {1\over
2}(P + \sqrt{D}), b = {1\over 2}(P - \sqrt{D}), D = P↑2 - 4Q$.
Then $2↑{n-1}U↓n = \sum ↓k({n\atop 2k+1})P↑{n-2k-1}D↑k$; so
$U↓p ≡ D↑{(p-1)/2}\modulo p$ if $p$ is an odd prime. similarly,
if $V↓n = a↑n + b↑n = U↓{n+1} - QU↓{n-1}$, then $2↑{n-1}V↓n
= \sum ↓k ({n\atop 2k})P↑{n-2k}D↑k$, and $V↓p ≡ P↑n ≡ P$. Thus
if $U↓p ≡ -1$, we find that $U↓{p+1}$ mod $p = 0$. If $U↓p ≡
1$, we find that $(QU↓{p-1})$mod $p = 0$; here if $Q$ is a multiple
of $p, U↓n ≡ P↑{n-1}\modulo p$ for $n > 0$, so $U↓n$ is
never a multiple of $p$; if $Q$ is not a multiple of $p, U↓{p-1}$
mod $p = 0$. Therefore as in Theorem L\null, $U↓t$ mod $N = 0$ if
$N = p↑{e↓1}↓{1} \ldotss p↑{e↓r}↓{r}$, gcd($N, Q) = 1$, and $t
=$ lcm↓{1≤j≤r}\biglp p↑{e$↓j-1}↓{j}(p↓j + ε↓j)\bigrp $. Under
the assumptions of this exercise, the rank of apparition of
$N$ is $N + 1$; hence $N$ is prime to $Q$ and $t$ is a multiple
of $N + 1$. Also, the assumptions of this exercise imply that
each $p↓j$ is odd and each $ε↓j$ is \pm 1, so $t ≤ 2↑{1-r} ??7p↑{e↓j-1}↓{j}(p↓j
+ {1\over 3}p↓j) = 2({2\over 3})↑rN$; hence $r = 1$ and $t =
p↑{e↓1}↓{1} + ε↓1p↑{e↓1-1}↓{1}$. Finally, therefore $e↓1 = 1$
and $ε↓1 = 1$.

Note{\sl : }Obviously if this test for primality
is to be any good, we must choose $P$ and $Q$ in some way that
makes it likely that the test will work. Lehmer suggests taking
$P = 1$ so that $D = 1 - 4Q$, and choosing $Q$ si that gcd($N,
QD) = 1$. (If the latter condition fails, we know already that
$N$ is not prime, unless $|Q| ≥ N.)$ Furthermore, the derivation
above shows that we will want $ε↓1 = 1$, that is, $D↑{(N-1)/2}
≡ -1\modulo N$. This is another condition that determines
the choice of $Q$. Furthermore, if $D$ satisfies this condition,
and if $U↓{N+1}$ mod $N ≠ 0$, we know that $N$ is {\sl not}
prime.

{\sl Example{\sl : }}If $P = 1, Q = -1$, we have
the Fibonacci sequence, with $D = 5$. Since 5$↑{11} ≡ -1 (modulo
23), we might attempt to prove that 23 is prime by using the
Fibonacci sequence:$
$$$\langle F↓n$ mod 23\rangle = 0, 1, 1, 2, 3, 5, 8, 13, 21,
11, 9, 20, 6, 3, 9, 12, 21, 10, 8, 18, 3, 21, 1, 22, 0, . .
.
|qctr \9skip |newtype so 24 is the rank of apparition of 23
and the test works. However, the Fibonacci sequence cannot be
used in this way to prove the primality of 13 or 17, since $F↓7$
mod 13 = 0 and $F↓9$ mod 17 = 0. When $p ≡ \pm 1\modulo{10}$,
we have 5↑{$(p-1)/2}$ mod $p = 1$, so $F↓{p-1}$ (not $F↓{p+1})$
is divisible by $p$.

\ansno 13. Let $f(q) = 2$ lg $q - 1$. When $q = 2$ or 3, the
tree has at most $f(q)$ nodes. When $q > 3$ is prime, let $q
= 1 + q↓{11} \ldotsm q↓t$ where $t ≥ 2$ and $q↓1, \ldotss , q↓t$
are prime. The size of the tree is $≤1 + \sum f(q↓k) = 2 + f(q
- 1) - t < f(q). [{\sl SIAM J. Comp.\ \bf 7} (1975), 214--220.]

\ansno 18. $x\biglp G(α) - F(α)\bigrp$ is the number of $n ≤
x$ whose second-largest prime factor is ≤$x↑|≤a$ and whose largest
prime factor is $>x↑|≤a$. Hence $xG↑\prime (t) dt = \biglp π(x↑{t+dt})
- π(x↑t)\bigrp . x↑{1-t}\biglp G(t/(1 - t)\bigrp - F\biglp t/(1
- t))\bigrp $. The probability that $p↓{t-1} ≤ \sqrt{p↓t}$ is
\int ↑{1}↓{0} $F\biglp t/2(1 - t)\bigrp t↑{-1} dt. [$Numerical
evaluation yields .62433. Curiously, it can be shown that this
also equals $\int ↑{1}↓{0} F\biglp t/(1 - t)\bigrp dt$, the
average value of log $p↓t/$log $x$. The derivative $G↑\prime
(0)$ can be shown to equal $\int ↑{1}↓{0} F\biglp t/(1 - t)\bigrp
t↑{-2} dt = F(1) + 2F({1\over 2}) + 3F({1\over 3}) +\cdots
= 1.78107$. The third-largest prime factor has $H(\gamma
) = \int ↑{\gamma }↓{0} \biglp H(t/(1 - t)) - G(t/(1 - t))\bigrp
t↑{-1} dt$ and $H↑\prime (0) = ∞$. See D. E. Knuth and L. Trabb-Pardo,
to appear.]

\ansno 19. $M = 2↑D - 1$ is a multiple of all $p$ for which
the order of 2 modulo $p$ divides $D$. Let $a↓1 = 2$ and $a↓{j+1}
= a↑{q↓j}↓{j}$ mod $N$, where $q↓j = p↑{e↓j}↓{j}, p↓j$ is the
$j$th prime, and $e↓j = \lfloor$ log 1000/log $p↓j\rfloor $;
let $A = a↓{169}$. Now compute $b↓q =$ gcd($A↑q - 1, N)$ for
all primes $q$ between 10$↑3 and 10↑5. One way to do this is
to start with A↑{1009}$ mod $N$ and then to multiply alternately
by $A↑4$ mod $N$ and $A↑2$ mod $N$. (A similar method was used
in the 1920s by D. N. Lehmer, but he didn't publish it.) As
with Algorithm B we can avoid most of the gcd's by batching;
e.g., since $b↓{30-k} =$ gcd($A↑{30r} - A↑k, N)$ we might try
batches of 8, computing $c↓r = (A↑{30r} - A↑{29})(A↑{30r} -
A↑{23}) \ldotsm (A↑{30r} - A)$ mod $N$, then gcd($c↓r, N)$ for
33 < $r ≤ 3334$.

%folio 795 galley 11b (C) Addison-Wesley 1978	-
|qleft \24skip |newtype {\:r SECTION 4.6

\ansno 1. $9x↑2 + 7x + 9; 5x↑3 + 7x↑2
+ 2x + 6$.

\ansno 2. (a) True.\xskip (b) False if the algebraic
system $S$ contains ``zero divisors'', nonzero numbers whose
product is zero, as in exercise 1; otherwise true.\xskip (c) False;
($x + 1) + \biglp (-1)x + 0\bigrp = 1$.

\ansno 3. Assume that $r ≤ s$. For $0
≤ k ≤ r$ the maximum is $m↓1m↓2(k + 1)$; for $r ≤ k ≤ s$ it
is $m↓1m↓2(r + 1)$; for $s ≤ k ≤ r + s$ it is $m↓1m↓2(r + s
+ 1 - k)$. The least upper bound valid for all $k$ is $m↓1m↓2(r
+ 1)$. (The solver of this exercise will know how to factor
the polynomial $x↑7 + 2x↑6 + 3x↑5 + 3x↑4 + 3x↑3 + 3x↑2 + 2x
+ 1.)$

\ansno 4. If the polynomials each have fewer than
2$↑t$ nonzero coefficients, the product can be formed by putting
exactly $t - 1$ zeros between each of the coefficients, then
multiplying in the binary number system, and finally using a
logical AND operation (present on most binary computers, cf.\
Section 4.5.4) to zero out the extra bits. For example if $t
= 3$, the multiplication in the text would become (1001000001)$↓2
\times (1000001001)↓2 = (100-00-0--00-00-00-)↓2$; if we AND
the result with the constant (1001001 \ldotsm 1001)$↓2, the desired
answer is obtained. A similar technique can be used to multiply
polynomials with nonnegative coefficients when it is known that
the coefficients will not be too large$.

\ansno 5. Polynomials of degree $≤2n$ can be represented
as $U↓1(x)x↑n + U↓0(x)$ where deg$ (U↓1)$, deg $(U↓0) ≤ n$;
and $\biglp U↓1(x)x↑n + U↓0(x)|newtype )(|newtype V↓1(x)x↑n
+ V↓0(x)\bigrp = U↓1(x)V↓1(x)(x↑{2n} + x↑n) + \biglp U↓1(x)
+ U↓0(x)|newtype )(|newtype V↓1(x) + V↓0(x)\bigrp x↑n + U↓0(x)V↓0(x)(x↑n
+ 1)$. (This equation assumes that arithmetic is being done
modulo 2.) Thus Eqs.\ 4.3.3--3, 4, 5 hold.
|qleft $\qquad Note{\sl : }$S. A. Cook has shown that Algorithm
4.3.3C can be extended in a similar way, and exercise 4.6.4--14
describes a method requiring even fewer operations for large
$n$. But these ideas are not useful for ``sparse'' polynomials
(having mostly zero coefficients).

%folio 796 galley 11c (C) Addison-Wesley 1978	-
|qleft \24skip |newtype {\:r SECTION 4.6.1

\ansno 1. $Q(X) = 1 \cdot 2↑3x↑3 + 0
\cdot 2↑2x↑2 - 2 \cdot 2x + 8 = 8x↑3 - 4x + 8; r(x) = 28x↑2
+ 4x + 8$.

\ansno 2. The monic sequence of polynomials produced
during Euclid's algorithm has the coefficients (1, 5, 6, 6,
1, 6, 3), (1, 2, 5, 2, 2, 4, 5), (1, 5, 6, 2, 3, 4), (1, 3,
4, 6), 0. Hence the greatest common divisor is $x↑3 + 3x↑2 +
4x + 6$. (The greatest common divisor of a polynomial and its
reverse is always symmetric, in the sense that it is a unit
multiple of its own reverse.)

\ansno 3. The procedure of Algorithm 4.5.2X is
valid, with polynomials over $S$ substituted for integers. When
the algorithm terminates, we have $U(x) = u↓2(x), V(x) = u↓1(x)$.
Let $m =$ deg$(u), n =$ deg$(v)$. It is easy to prove by induction
that deg($u↓3) +$ deg($v↓1) = n$, deg$(u↓3) +$ deg$(v↓2) = m$,
after step X3, throughout the execution of the algorithm, provided
that $m ≥ n$. Hence if $m$ and $n$ are greater than $d =$ deg\biglp
gcd($u, v)\bigrp$ we have deg($U) < m - d$, deg($V) < n - d$;
the exact degrees are $m - d↓1$ and $n - d↓1$, where $d↓1$ is
the degree of the second-last nonzero remainder. If $d =$ min$(m,
n)$, say $d = n$, we have $U(x) = 0, V(x) = 1$.

When $u(x) = x↑m - 1$ and $v(x) = x↑n - 1$, the
identity $(x↑m - 1)$mod$(x↑n - 1) = x↑$${mmodn} - 1$ shows that
all polynomials occurring during the calculation are monic with
integer coefficients. When $u(x) = x↑{21} - 1, v(x) = x↑{13}
- 1$, we have $V(x) = (x↑{11} + x↑8 + x↑6 + x↑3 + 1), U(x) =
-(x↑{19} + x↑{16} + x↑{14} + x↑{11} + x↑8 + x↑6 + x↑3 + x)$.
[See also Eq.\ 3.3.3--29, which gives an alternative formula
for $U(x), V(x).]$
Programming\quad (Knuth/A.-W.)\quad f. 797\quad ch. 4\quad g
12c
\ansno 4. Since the quotient $q(x)$ depends only on $v(x)$
and the first $m - n$ coefficients of $u(x)$, the remainder
$r(x) = u(x) - q(x)v(x)$ is uniformly distributed and independent
of $v(x)$. Hence each step of the algorithm may be regarded
as independent of the others; this algorithm is much more well-behaved
than Euclid's algorithm over the integers.

The probability that $n↓1 = n - k$ is $p↑{1-k}(1
- 1/p)$, and $t = 0$ with probability $p↑{-n}$. Each succeeding
step has essentially the same behavior; hence we can see that
any given sequence of degrees $n, n↓1, \ldotss , n↓t, -∞$ occurs
with probability $(p - 1)↑t/p↑n$. To find the average value
of $f(n↓1, \ldotss , n↓t)$, let $S↓t$ be the sum of $f(n↓1, \ldotss
, n↓t)$ over all sequences $n > n↓1 >\cdots > n↓t
≥ 0$ having a given value of $t$; then the average is $\sum
↓t S↓t(p - 1)↑t/p↑n$.
|qleft |newtype \qquad Let $f(n↓1, \ldotss , n↓t) = t$; then
$S↓t = (↑{n}↓{t})(t + 1)$, so the average is $n(1 - 1/p)$. Similarly,
if $f(n↓1, \ldotss , n↓t) = n↓1 +\cdots + n↓t$, then
$S↓t = (↑{n}↓{2})(↑{n-1}↓{t-1})$, and the average is $(↑{n}↓{2})(1
- 1/p)$. Finally, if $f(n↓1, \ldotss , n↓t) = (n - n↓1)n↓1 +\cdots
+ (n↓{t-1} - n↓t)n↓t$ then $S↓t = (↑{n+2}↓{t+2})
- (n + 1)(↑{n+1}↓{t+1}) + (↑{n+1}↓{ 2})(↑{n}↓{t})$, and the
average is $(↑{n+1}↓{ 2}) - (n + 1)p/(p - 1) + \biglp p/(p -
1)\bigrp ↑2(1 - 1/p↑{n+1})$.

As a consequence we can see that if $p$ is large
there is very high probability that $n↓{j+1} = n↓j - 1$ for
all $j$. (If this condition fails over the rational numbers,
it fails for all $p$, so we have further evidence for the text's
claim that Algorithm C almost always finds $t↓3 =\cdots
= 2.)$

\ansno 5. Using the formulas developed
in exercise 4, with $f(n↓1, \ldotss , n↓t) = \delta ↓n|infinf
t↓0$, we find the probability is $1 - 1/p$ if $n > 0, 1$ if
$n = 0$.

\ansno 6. Assuming that the constant terms $u(0)$
and $v(0)$ are nonzero, imagine a ``right-to-left'' division
algorithm, $u(x) = v(x)q(x) + x↑{m-n}r(x)$, deg$(r) <$ deg$(v)$.
We obtain a gcd algorithm anlogous to Algorithm 4.5.2B\null, which
is essentially Euclid's algorithm applied to the ``reverse''
of the original inputs (cf.\ exercise 2), afterwards reversing
the answer and multiplying by an appropriate power of $x$.

\ansno 7. The units of $S$ (as polynomials of degree
zero).

|qleft ??????|newtype 58320---Computer
%folio 797 galley 12 (C) Addison-Wesley 1978	-
\ansno 8. If $u(x) = v(x)w(x)$, where $u(x)$ has
integer coefficients while $v(x)$ and $w(x)$ have rational coefficients,
there are integers $m$ and $n$ such that $m 0 v(x)$ and $n \cdot
w(x)$ have integer coefficients. Now $u(x)$ is primitive, so
we have
$$$u(x) = \pm$ PP\biglp $m 0 v(x)\bigrp$ pp\biglp $n \cdot w(x)\bigrp
$.

\ansno 9. We can extend Algorithm E as follows:
Let \biglp $u↓1(x), u↓2(x), u↓3, u↓4(x)\bigrp$ and \biglp $v↓1(x),
v↓2(x), v↓3, v↓4(x)\bigrp$ be quadruples satisfying the relations
$u↓1(x)u(x) + u↓2(x)v(x) = u↓3u↓4(x), v↓1(x)u(x) + v↓2(x)v(x)
= v↓3v↓4(x)$. The extended algorithm starts with \biglp 1, 0,
cont$(u)$, pp($u(x))\bigrp$ and \biglp 0, 1, cont($v)$, pp$(v(x))\bigrp$
and manipulates these quadruples in such a way as to preserve
the above conditions, where $u↓4(x), v↓4(x)$ run through the
same sequence as $u(x), v(x)$ do in Algorithm E\null. If $au↓4(x)
= q(x)v↓4(x) + br(x)$, we have $av↓3\biglp u↓1(x), u↓2(x)\bigrp
- q(x)u↓3\biglp v↓1(x), v↓2(x)\bigrp = \biglp r↓1(x), r↓2(x)\bigrp
$, where $r↓1(x)u(x) + r↓2(x)v(x) = bu↓3v↓3r(x)$, so the extended
algorithm can preserve the desired relations. If $u(x)$ and
$v(x)$ are relatively prime, the extended algorithm eventually
finds $r(x)$ of degree zero, and we obtain $U(x) = r↓2(x), V(x)
= r↓1(x)$ as desired. (In practice we would divide $r↓1(x),
r↓2(x)$, and $bu↓3v↓3$ by gcd\biglp cont$(r↓1)$, cont($r↓2)).\bigrp$
Conversely, if such $U(x)$ and $V(x)$ exist, then $u(x)$ and
$v(x)$ have no common prime divisors, since they are primitive
and have no common divisors of positive degree.

\ansno 10. By successively factoring polynomials
that are reducible into polynomials of smaller degree, we must
obtain a finite factorization of any polynomial into irreducibles.
The factorization of the {\sl content} is unique. To show that
there is at most one factorization of the primitive part, the
key result is to prove that if $u(x)$ is an irreducible factor
of $v(x)w(x)$, but not a unit multiple of the irreducible polynomial
$v(x)$, then $u(x)$ is a factor of $w(x)$. This can be proved
by observing that $u(x)$ is a factor of $v(x)w(x)U(x) = rw(x)
- w(x)u(x)V(x)$ by the result of exercise 9, where $r$ is a
nonzero constant.

\ansno 11. The only row names needed to
show that $u↓4(x)$ has integer coefficients are $A↓1, A↓0, B↓4,
B↓3, B↓2, B↓1, B↓0, C↓1, C↓0, D↓0$. In general, let $u↓{j+2}(x)
= 0$; then the rows needed for the proof are $A↓n|infinf 2↓{-n}|infinf
j$ through $A↓0, C↓n|infinf 2↓{-n}|infinf j$ through $C↓0, D↓n|infinf
3↓{-n}|infinf j$ through $D↓0$, etc.

\ansno 12. If $n↓k = 0$, the argument in the text can be modified
to show that the absolute value of the determinant is $??3↑{n↓{k-1}}↓{k}/??7↓{1<j<k}
??3↑{(t↓j-1)(t↓{j+1}-2)}↓{j}$. If the polynomials have a factor
of positive degree, we can artificially assume that the polynomial
zero has degree zero and use the above formula for $??3↓k =
0. Note{\sl : }$The value $R(u, v)$ of Sylvester's determinant
is called the {\sl resultant} of $u$ and $v$, and the quantity
(-1)↑{deg$(u)($deg($u)-1)/2} ??3(u)↑{-1}R(u, u↑\prime )$ is
called the {\sl discriminant} of $u$. If $u(x) = a(x - α↓1)
\ldotsm (x - α↓m)$ and $v(x) = b(x - β↓1) \ldotsm (x - β↓n)$,
we have $R(u, v) = a↑nv(α↓1) \ldotsm v(α↓m) = (-1)↑{mn}b↑mu(β↓1)
\ldotsm u(β↓n) = a↑nb↑m ??7↓{1≤i≤m,1≤j≤n}(α↓i - β↓j)$. It follows
that the polynomials of degree $mn$ in $y$ defined as the respective
resultants of $u(y - x), u(y + x), x↑mu(y/x)$, and $u(yx)$ with
$v(x)$ have as respective roots the sums $α↓i + β↓j$, differences
$α↓i - β↓j$, products $α↓iβ↓j$, and quotients $α↓i/β↓j \biglp$
when $v(0) ≠ 0\bigrp $. This idea has been used by R. G. K.
Loos to construct algorithms for arithmetic on algebraic numbers
[{\sl SIAM J. Computing}, to appear].

If we replace each row $A↓i$ in Sylvester's matrix
by
$$$(b↓0A↓i + b↓1A↓{i+1} +\cdots + b↓n|infinf 2↓{-1-i}A↓n|infinf
2↓{-1}) - (a↓0B↓i + a↓1B↓{i+1} + \cdots + a↓n|infinf
2↓{-1-i}B↓n|infinf 2↓{-1})$,
|qctr \9skip |newtype and then delete rows B$↓n|infinf 2↓{-1}$
through $B↓0$ and the last $n↓2$ columns, we obtain an $n↓1
\times n↓1$ determinant for the resultant instead of the original
$(n↓1 + n↓2) \times (n↓1 + n↓2)$ determinant. In some cases
the resultant can be evaluated efficiently by means of this
determinant; see {\sl CACM \bf 12} (1969), 23--30, 302--303.

\ansno 13. If $??3↑{t↓k}↓{k}u↓{k-1}(x)
= u↓k(x)q↓{k-1}(x) + ??3↑{t↓{k-1}}↓{k-1}u↓{k+1}(x)$ then $(??3↓k??3↑x|infsup
↑{+1})↑t|infsup k??l↑{x↓{k-1}}w(x)u↓{k-1}(x) = ??3↑x|infsup
kw(x)u↓k(x)??3↑y|infsup kq(x) + (??3↓{k-1}??3↑{x↓{k-1}+1})↑{t↓{k-1}}??3↑{x↓{k+1}}w(x)u↓{k+1}(x)$;
so the new $u↓k(x)$ is $??3↑{x↓k}w(x)u↓k(x)$, where $x↓1 = x↓2
= t↓1 = 0, x↓{k+1} = x↓kt↓k - x↓{k-1}(t↓{k-1} - 1) + t↓k - t↓{k-1}$.

\ansno 14. Let $p$ be a prime of the domain, and let $j,k$ be
maximum such that $p↑k\rslash v↓n = ??3(v), p↑j\rslash v↓{n-1}$.
Let $P = p↑k$. By Algorithm R we may write $q(x) = a↓0 + Pa↓1x
+\cdots + P↑sa↓sx↑s$, where $s = m - n ≥ 2$. Let
us look at the coefficients of $x↑{n+1}, x↑n$, and $x↑{n-1}$
in $v(x)q(x)$, namely $Pa↓1v↓n + P↑2a↓2v↓{n-1} +\cdotss, a↓0v↓n
+ Pa↓1v↓{n-1} +\cdotss, a↓0v↓{n-1} + Pa↓1v↓{n-2} +\cdotss$,
each of which is a multiple of $P↑3$. We conclude from the first
that $p↑j\rslash a↓1$, from the second that $p↑{$min($k,2j)}\rslash
a↓0$, then from the third that $P\rslash a↓0$. Hence $P\rslash
r(x)$. [If $m$ were only $n + 1$, the best we could prove would
be that $p↑{\lceil k/2\rceil }$ divides $r(x)$; e.g., consider
$u(x) = x↑3 + 1, v(x) = 4x↑2 + 2x + 1, r(x) = 18$. By considering
an algorithm for computing polynomial resultants, W. S. Brown
has generalized this exercise in a different way (to appear).]
|qleft ??????|newtype
%folio 800 galley 13 (C) Addison-Wesley 1978	-
58320---Computer Programming\quad (Knuth/A.-W.)\quad Ch. 4\quad
f. 800\quad g. 13c
\ansno 15. Let $c↓{ij} = a↓{i1}a↓{j1} +\cdots +
a↓{in}a↓{jn}$; we may assume that $c↓{ii} > 0$ for all $i$.
If $c↓{ij} ≠ 0$ for some $i ≠ j$, we can replace row $i$ by
$(a↓{i1} - ca↓{j1}, \ldotss , a↓{in} - ca↓{jn})$, where $c =
c↓{ij}/c↓{jj}$; this does not change the value of the determinant,
and it decreases the value of the upper bound we wish to prove,
since $c↓{ii}$ is replaced by $c↓{ii} - c↑{2}↓{ij}/c↓{ij}$.
These replacements can be done in a systematic way for increasing
$i$ and for $j < i$, until $c↓{ij} = 0$ for all $i ≠ j$. (The
latter algorithm is called ``Schmidt's orthogonalization process'';
see {\sl Math.\ Annalen \bf 63} (1907), 442.) Then det$(A)↑2
= det(AA↑T) = c↓{11} \ldotsm c↓{nn}$.

\ansno 16. Let $f(x↓1, \ldotss , x↓n) =
g↓m(x↓2, \ldotss , x↓n)x↑{m}↓{1} +\cdots + g↓0(x↓2,
\ldotss , x↓n)$, and let $g(x↓2, \ldotss , x↓n) = g↓m(x↓2, \ldotss
, x↓n)↑2 +\cdots + g↓0(x↓2, \ldotss , x↓n)↑2$; the
latter is not identically zero. We have $a↓N ≤ m(2N + 1)↑{n-1}
+ (2N + 1)b↓N$, where $b↓N$ is the number of integer solutions
of $g(x↓2, \ldotss , x↓n) = 0$ with variables bounded by $N$.
Hence lim$↓{N←∞} a↓N/(2N + 1)↑n =$ lim↑{$}↓{N←∞} b↓N/(2N + 1)↑{n-1}$,
and this is zero by induction.

\ansno 17. a) For convenience, let us describe the algorithm
only for $A = \{a, b\}$. The hypotheses imply that deg($Q↓1U)
=$ deg($Q↓2V) ≥ 0$, and deg($Q↓1) ≤$ deg($Q↓2)$. If deg($Q↓1)
= 0$, then $Q↓1$ is must a nonzero rational number, so we set
$Q = Q↓2/Q↓1$. Otherwise let $Q↓1 = aQ↓{11} + bQ↓{12} + r↓1,
Q↓2 = aQ↓{21} + bQ↓{22} + r↓2$, where $r↓1$ and $r↓2$ are rational
numbers; it follows that
$$$Q↓1U - Q↓2V = a(Q↓{11}U - Q↓{21}V) + b(Q↓{12}U - Q↓{22}V)
+ r↓1U - r↓2V$.
|qctr \9skip We must have either deg($Q↓{11}) =$ deg($Q↓1) -
1$ or deg($Q↓{12}) =$ deg($Q↓1) - 1$. In the former case, deg$(Q↓{11}U
- Q↓{21}V) <$ deg($Q↓{11}U)$, by considering the terms of highest
degree that start with $a$; so we may replace $(Q↓1, Q↓2)$
by $(Q↓{12}, Q↓{22})$ and repeat the process.

b) We may assume that deg($U) ≥$ deg($V)$. If
deg($R) ≥$ deg($V)$, note that $Q↓1U - Q↓2V = Q↓1R - (Q↓2 -
Q↓1Q)V$ has degree less than deg($V) ≤$ deg($Q↓1R)$, so we can
repeat the process with $U$ replaced by $R$; we obtain $R =
Q↑\prime V + R↑\prime , U = (Q + Q↑\prime )V + R↑\prime $, where
deg($R↑\prime ) <$ deg($R)$, so eventually a solution will be
obtained.

c) The algorithm of (b) gives $V↓1 = UV↓2 + R$,
deg($R) <$ deg$(V↓2)$; by homogeneity $R = 0$ and $U$ is homogeneous.

d) We may assume that deg$(V) ≤$ deg($U)$. If
deg($V) = 0$, set $W ← U$; otherwise use (c) to find $U = QV$,
so that $QVV = VQV, (QV - VQ)V = 0$. This implies that $QV =
VQ$, so we can set $U ← V, V ← Q$ and repeat the process.






For further details about the subject of this
exercise, see P. M. Cohn, {\sl Proc.\ Cambridge Phil.\ Soc.\ \bf 57}
(1961), 18--30. The considerably more difficult problem of characterizing
{\sl all} string polynomials such that $UV = VU$ has been solved
by G. M. Bergman [Ph.D. thesis, Harvard University, 1967].

\ansno 18. [P. M. Cohn, {\sl Transactions Amer.\ Math.\ Soc.\ \bf 109}
(1963), 332--356.]

|qleft \3skip |hangindent3\qquad {\bf C1.} Set $u↓1 ← U↓1, u↓2
← U↓2, v↓1 ← V↓1, v↓2 ← V↓2, z↓1 ← z↑\prime↓{2} ← w↓1 ← w↑\prime↓{2}
← 1, z↑\prime↓{1} ← z↓2 ← ← w↑\prime↓{1} ← w↓2 ← 0, n
← 0$.

|qleft \3skip \qquad {\bf C2.} (At this point the identities
given in the exercise hold, and also $u↓1v↓1 = u↓1v↓2; v↓2 =
0$ if and only if $u↓1 = 0.)$ If $v↓2 = 0$, the algorithm terminates
with gcrd($V↓1, V↓2) = v↓1$, lclm($V↓1, V↓2) = z↑\prime↓{1}V↓1
= -z↑\prime↓{2}V↓2$. (Also by symmetry gcld($U↓1, U↓2) =$
lclm($U↓1, U↓2) = U↓1w↓1 = -U↓2w↓2.)$

|qleft \3skip \qquad {\bf C3.} Find $Q$ and $R$ such that $v↓1
= Qv↓2 + R$, where deg($R) <$ deg($v↓2). \biglp$ We have $u↓1(Qv↓2
+ R) = u↓2v↓2$, so $u↓1R = (u↓2 - u↓1Q)v↓2 = R↑\prime v↓2.\bigrp$

|qleft  \3skip \qquad {\bf C4.} Set $(w↓1, w↓2, w↑\prime↓{1},
w↑\prime↓{2}, z↓1, z↓2, z↑\prime↓{1}, z↑\prime↓{2},
u↓1, u↓2, v↓1, v↓2) ← (w↑\prime↓{1} - w↓1Q, w↑\prime↓{2}
- w↓2Q, w↓1, w↓2, z↑\prime↓{1}, z↑\prime↓{2}, z↓1 - Qz↑\prime↓{1},
z↓2 - Qz↑\prime↓{2}, u↓2 - u↓1Q, u↓1, v↓2, v↓1 - Qv↓2)$ and
$n ← n + 1$. Go back to C2.
|qleft β?????\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad